又见背包问题
我想说的是看到第一眼就知道是一个二人背包问题,介于本人懒惰,不想去思考其状态方程,于是就大胆地敲DFS 结果肯定超时了,对于这道题 思路:dp[i][j][k]表示当第一个背包里放重量恰为i,第二个背包里放重量恰为j时,当前物品放在k号背包里所得到的最大价值,k=0表示两个背包都不放 状态转移是:dp[i][j][0] = max(dp[i][j][0],dp[i][j][1],dp[i][j][2]); dp[i][j][1] = max(dp[i-w[k]][j][0],dp[i-w[k]][j][2])+v[k]; dp[i][j][2] = max(dp[i][j-w[k]][1],dp[i][j-w[k]][0])+v[k]; 边界条件是: dp[0][0][0]=0; dp[w[0]][0][1] = v[0]; dp[0][w[0]][2] = v[0];