题目描述
有一个容量为V的背包，还有n个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积w和价值v。 问：如何向背包装物体才能使背包中物体的总价值最大？
解题
- 确定状态表示，dp[]表示的是什么
在这道题中dp[i][j]指的是在背包容量为j时，从1到第i件物品中选择若干物品后，背包内物品的最大价值 - 确定初始状态（边界条件），当背包容量为0或没有放置任何物品时，背包内物品价值为0，即
dp[i][0]和dp[0][j]都为0 - 确定状态转移方程，当背包容量可以装下第i件物品，即可以选择放不放第i件物品
- 不放，则背包内物品价值
dp[i][j]=dp[i-1][j] - 放，此时背包容量减少，
dp[i][j]=dp[i-1][j-wight[i]]+value[i]所以dp[i][j]=max(dp[i-1][j],dp[i-1][j-wight[i]]+value[i])遍历顺序如下：
- 不放，则背包内物品价值
进阶：转换为一维数组
仍然需要进行n*V次遍历，但这次需要从后向前遍历,每一层遍历的终止条件为j<w[i]（即不做修改，相当于直接继承上一层的状态）
即dp[j]=max(dp[j-w]+value[i],dp[j])