完全背包

userId_undefined
编程_Hyperion_漩涡鸣人
空间掌握者快排信徒→排序之神冒泡宗师→排序元老进制转换师多键裁决者结构体学徒→封装者

2026-08-30 17:44:16

发布于：上海

2阅读
0回复
0点赞

完全背包：与01背包唯一的区别是——每种物品有无限件，可以拿任意多个。
DP决策：与01背包完全相同，可以选择拿还是不拿。

状态定义：dp[i][j]表示前i个物品，容量为j时能取到的最大价值。
转移方程：

for(int i=1;i<=n;i++){
    for(int j=0;j<=w[i];j++){
       if(j>=w[i])dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
       else dp[i][j]=dp[i-1][j]; 
    }
}
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论