题目描述
有一个容量为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])