01背包
2025-06-14 16:42:23
发布于：浙江
1阅读
0回复
0点赞
物品价值：c[i]
物品体积：v[i]
背包容量：w
物品数量：n
01背包：
二维：
1.确定状态：dp[i][j]表示选择前i件商品容量j下的最大价值
2.状态转移方程是：
dp[i][j]=dp[i-1][j]; 背包容量不够装，直接转移上一件
j<v[i]
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]) 前提：背包能装下
j>=v[i]
dp[i-1][j]：不选，全部容量选上一件
c[i]+dp[i-1][j-v[i]]：选，这件商品的价值+剩余容量选上一件商品的价值
3.初始值：什么都不选的价值为0
4.返回结果；dp[n][w];
一维：
1.确定状态：dp[j]表示选择前i件商品容量j下的最大价值
2.状态转移方程是：
dp[j]=max(dp[j],dp[j-v[i]]+c[i]) 前提：背包能装下
j>=v[i]
dp[j]：不选，全部容量选上一件
c[i]+dp[j-v[i]]：选，这件商品的价值+剩余容量选上一件商品的价值
3.初始值：什么都不选的价值为0
4.返回结果；dp[n][w];
01背包一维背包必须逆向循环 w~0
这里空空如也
有帮助，赞一个