完全背包

userId_undefined
Dry31
时间刺客空间掌握者俄罗斯套娃大师

2026-08-30 18:04:20

发布于：上海

1阅读
0回复
0点赞

完全背包：与01背包唯一的区别是——每种物品有无限件。
DP决策：和01背包完全相同，可以拿或不拿。
状态定义：dp[i][j]表示前i个物品，容量为j时能取到的最大价值。
转移方程：
if(j>=w[i]){
dp[j]=max({dp[j],dp[j-w[i]]+v[i]});
}else{
dp[j]=dp[j];
}
滚动数组优化：
for(int i=1;i<=n;i++){
for(int j=wi[];j<=m;j++){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论