完全背包问题

? ! 白白！？

2026-08-29 11:32:32

发布于：上海

1阅读

0回复

0点赞

完全背包

完全背包：与01背包唯一的区别是——每种物品有无限件，可以拿任意多个。
二维数组的写法：
01背包：

for(int i = 1;i <= m;i++){
        for(int j = 0;j <= t;j++){
            if(j >= w[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            else dp[i][j] = dp[i - 1][j];
        }
}

完全背包：

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

滚动数组优化：
01背包：

int dp[j];//表示容量为 j 时背包最大价值
for(int i = 1;i <= n;i++){
    for(int j = w[i];j >= 0;j--){
        if(j >= w[i]) dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
        //j < w[i], 继承正上方的值，恰好就是 dp[j] 不动
    }
}

完全背包：

for(int i = 1;i <= n;i++){ //便利所有物品
        for(int j = 0];j <= m;j++){ //正序遍历容量，可以重复拿
            if(j >= w[i]) dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
        }
}

状态定义：