动态规划解决背包问题

背包问题——动态规划

一、单副本背包（经典的0/1背包问题）
问题描述：

单副本背包问题：
共有N件物品与一个容量为V的背包。
每个第i个物品占据体积c[i]的空间，并具有大小为w[i]的价值。

我们的目标是确定哪些物品应被放入背包以实现总价值的最大化。

分析：

用f[i][v]表示前i件物品放入一个容量为v的背包可以获得的最大价值，如果我们能计算出所有f[i][v]的值，那么f[N][V]就是答案

用动态规划算法解决问题的主要思路就是将原问题转化为规模更小的子问题.
因此我们假设对于只有i-1件物品的情况下，我们已经求得背包容量为0到V时的最优值，也就是说所有的f[i-1][v]的值都已求出
我们再来考虑有i件物品的情况，如果第i件物品不放进容量为v的背包，则f[i][v] = f[i-1][v].
如果第i件物品放进容量为v的背包，则f[i][v] = f[i-1][v-c[i]] + w[i]. 这种情况只有当v>=c[i]时才有可能.
最后，我们还需要再考虑一下动态规划的边界条件，当i=0，也就是没有任何物品的情况下，显然对于任意的容量v，f[0][v]=0
综上，我们可以得到动态规划的状态转移方程：