又见背包问题
我想说的是看到第一眼就知道是一个二人背包问题,介于本人懒惰,不想去思考其状态方程,于是就大胆地敲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];
© 2015 HUST ACMICPC TEAM. All Right Reserved.