DP中貌似分析出状态转移方程是很重要的.(就像高中数学的递推表达式…

那么分析一下这个问题的状态转移. 假定有dp[i][j]表示从前i个物品中选出总重量不超过j的物品时的最大价值. 很显然dp[0][j] = 0. 对于任一i, j, 如果w[i] > j那么dp[i+1][j] = dp[i][j], 否则dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]). 公式如下:

参考代码:

感谢kid177! 把上面的代码降到了一维~

完全背包问题

有n种重量和价值分别为w i , v i 的物品. 从中挑选总重量不超过W的物品, 求价值总和的最大值. 每种物品可以挑选任意多件.

还是用上面的dp[i][j]那么现在递推关系变成了这样:

然后注意一下在dp[i+1][j]中选择k(k>=1)个的情况与在dp[i+1][j-w[i]]中选择k+1个情况相同. 所以dp[i+1][j]中k>=1的部分已经在dp[i+1][j-w[i]]中计算过. 上面的式子可以这样变形:

参考代码:

多重部分和问题

有n种不同大小的数字a i , 每种各m i 个. 判断是否可以从这些数字中选出若干使它们的和恰好为K.

用dp[i][j]表示前i种数相加得到j的时候第i种数最多能剩余多少个(不能得到j的时候为-1). 那么如果前i-1种数相加能得到j的话, 第i个数就可以留下m i 个; 如果前i种数加和为j-a i 时时第i种数还剩下k(k>0)个的话, 那么dp[i][j]就等于k-1. 这样可以得到下面的递推式: