08/30 第42课笔记完全背包

Kaito

2026-08-30 18:02:57

发布于：上海

3阅读

0回复

0点赞

08/30 第42课笔记完全背包

完全背包:

与01背包唯一的区别是——每种物品有无限件，可以拿任意多个

完全背包的决策，状态，转移方程

DP决策：

和01背包完全相同，可以选择拿或者不拿。

状态定义：

dp[i][j]表示前i个物品，容量为j时能取到的最大价值。

转移方程：

  dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);

示例代码：

for(int i=1;i<=n;i++){
    for(int j=0;j<=m;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];
    }
}

一维优化

滚动数组优化

for(int i=1;i<=n;i++){
    for(int j=0;j<=m;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];
    }
}