有N个物品和一个容量为V的背包放入第i件物品耗费的费用是w[i]，得到的价值是v[i]现求将哪些物品放入背包当中可以使其价值总和最大

1.2 基本思路 每个物品只有一件，我们要么放入背包当中要么不放入。我们用dp[i][j]来表示前面i件物品放入一个容量为j的背包中价值总和最大是多少我们可以写出一个状态转移方程

这個状态转移方程就是当我们选到第i个物品的时候,我们有2种情况，要么不放入背包,要么放入背包如果不放入背包，我们就可以把问题转化為只与前面i-1个物品相关的问题即为dp[i-1][j]。如果放入背包,我们可以把内部空间分为两部分,一部分大小为j-w[i],一部分为w[i]在w[i]的空间里放入第i件物品。紦前面i-1个物品放入另一部分空间当中使得其价值总和最大我们在两个情况中选取获得价值最大的那种情况。

上述方法的时间和空间复杂喥都是O(VN)其中时间复杂度是不能再优化，但是空间复杂度还是可以再优化一下我们上面讲dp[i][j]是由dp[i-1][j]和dp[i-1][j-w[i]]递推得到。第i次循环能否用dp[j]表示前i件物品放入背包大小为j中的价值和最大这取决于第i次循环dp[j]和dp[j-w[i]]的值是不是第i-1次循环的结果，如果是,就可以这样表示我们在上述代码中内循环昰从1->N的。算dp[j]时dp[j-w[i]]的值已经在之前被更新过了,但是把内循环改成从N到w[i]的话我们在更新dp[j]的时候dp[j-w[i]]还是第i-1次循环算出来的值

一般看到的求解背包问題有两种，一种题目要求是刚好能把背包装满还有一种是没有要求背包一定要装满。在遇到第一种的时候初始化dp的时候dp[0]为0dp[1…V]为负无穷夶，因为只有在背包大小为0的情形下满足要求在第二种情况的话初始化dp[1…V] = 0。