动态规划算法_动态规划背包问题实例_0-1背包问题 动态规划

对容量为C的背包进行装载，从n个物品中选取装入背包的物品，每件物品的i重量为Wi、价值为Pi。对于可行的背包进行装载，背包中物品的总重量不能超过背包的容量。最佳装载是指所装入的物品价值最高。这里Xi=1表示物品i装入背包，Xi=0表示物品i不装入背包

分析

动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费过多的时间。0-1背包问题 动态规划动态规划法又和贪婪算法有些一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。

最优决策序列由最优决策子序列组成。假设f (i,y)表示剩余容量为y，剩余物品为i, i+1, …, n时的最优解的值，即：

f (n,y) = Pn, if y≥Wn

f (n,y) = 0, if 0≤y≤Wn

和

f (i,y) = max (f (i+1,y), f (i+1, y-Wi) + Pi) y≥Wi

f (i,y) = f (i+1,y) 0≤y≤Wi

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的，所以有必要将它详细解释一下：“将前i件物品放入容量为y的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为y的背包中”，价值为f[i-1][y]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为y-Wi的背包中”，此时能获得的最大价值就是f[i-1][y-Wi]再加上通过放入第i件物品获得的价值Pi。

权为整数的迭代方法

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-27431-1.html