🎒 背包问题全家桶复习笔记

帅树

2026-10-05 17:29:18

发布于：广东

10阅读

0回复

0点赞

知识点小结
背包问题是动态规划的经典模型，核心是在有限容量下选择物品，使总价值最大。三种背包的区别仅在于每件物品的数量限制，由此决定了遍历顺序和状态转移方式。

背包类型	物品数量限制	遍历顺序	核心思想
01背包	每件只能选 0 或 1 次	容量逆序遍历	保证每件物品只被选一次
完全背包	每件可以选无限次	容量正序遍历	允许同一物品被重复选取
多重背包	每件最多选 s[i] 次	枚举选取件数 k	在 0~s[i] 范围内尝试所有可能

状态转移方程（二维版）

dp[i][j] = max(dp[i-1][j - k*w[i]] + k*v[i])   其中 0 ≤ k ≤ min(j/w[i], s[i])

含义：对于第 i 件物品，尝试选 0 件、1 件、2 件……最多 k 件，取所有方案中的最大值。

一维滚动数组优化

背包逆序 防止同一物品被重复使用
完全背包正序 允许同一物品被重复使用
多重背包 根据 s[i] 的大小，退化为 01 背包或完全背包

二维数组版（多重背包通用模板）

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int w[N], v[N], s[N];       // w:重量, v:价值, s:数量
int dp[N][305];              // dp[i][j]: 前i件物品、容量j时的最大价值

int main(){
    int c, n;                // c:背包容量, n:物品数量
    cin >> c >> n;
    for(int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i] >> s[i];
    }

    for(int i = 1; i <= n; i++) {           // 枚举每件物品
        for(int j = 0; j <= c; j++){        // 枚举每个容量
            for(int k = 0; k <= min(j / w[i], s[i]); k++){
                // k: 当前物品选的件数，最多不能超过容量允许的数量和库存数量
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
                // 不选k件 vs 选k件（从上一行剩余容量转移过来）
            }
        }
    }
    cout << dp[n][c] << endl;
    return 0;
}

逐行说明：

const int N = 105;
int w[N], v[N], s[N];       // 三个数组分别存每件物品的重量、价值、可选数量
int dp[N][305];              // 二维dp表，第一维是物品编号，第二维是背包容量

int c, n;
cin >> c >> n;              // 读入背包容量和物品总数

for(int i = 1; i <= n; i++) {
    cin >> w[i] >> v[i] >> s[i];   // 读入每件物品的三个属性
}

for(int i = 1; i <= n; i++) {           // 外层：遍历每一件物品
    for(int j = 0; j <= c; j++){        // 中层：遍历背包的每个容量（0到c）
        for(int k = 0; k <= min(j / w[i], s[i]); k++){
            // 内层：枚举当前物品选几件
            // k 的上限取两个值的较小者：
            //   j / w[i] → 当前容量最多能装几件
            //   s[i]     → 该物品库存最多有几件
            
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
            // dp[i-1][j - k*w[i]] → 上一件物品、剩余容量的最大价值
            // k * v[i]            → 当前选k件带来的价值
            // 两者相加 = 选k件当前物品后的总价值
            // 与之前的 dp[i][j] 取最大值
        }
    }
}

cout << dp[n][c] << endl;   // 输出：前n件物品、容量c时的最大价值

一维滚动数组版（混合背包优化）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int w[N], v[N], s[N];
int dp[N];                   // 一维dp数组，dp[j]表示容量j时的最大价值

int main()
{
    int t, n;                // t:背包容量, n:物品数量
    cin >> t >> n;
    for(int i = 1; i <= n; i++)
        cin >> w[i] >> v[i] >> s[i];

    for(int i = 1; i <= n; i++) {
        if(s[i] == 0){       // 完全背包：数量无限制
            for(int j = w[i]; j <= t; j++) {      // 正序遍历
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        else if(s[i] == 1){  // 01背包：只能选1件
            for(int j = t; j >= w[i]; j--) {      // 逆序遍历
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        else{                // 多重背包：有限数量
            if(s[i] > t / w[i]){   // 数量超过容量能装的上限 → 等价于完全背包
                for(int j = w[i]; j <= t; j++) {  // 正序
                    dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
                }
            }
            else{            // 数量较少 → 拆成 s[i] 个01背包
                for(int k = 1; k <= s[i]; k++){
                    for(int j = t; j >= w[i]; j--) {  // 逆序
                        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
                    }
                }
            }
        }
    }
    cout << dp[t] << '\n';
}

逐行说明：

int dp[N];                 // 一维数组，节省空间，每次在原数组上更新

if(s[i] == 0){             // s[i]==0 表示完全背包（无数量限制）
    for(int j = w[i]; j <= t; j++) {   // 正序：从小到大遍历容量
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        // 正序保证 dp[j-w[i]] 可能已经包含当前物品，从而实现重复选取
    }
}

else if(s[i] == 1){        // 01背包（只能选1件）
    for(int j = t; j >= w[i]; j--) {   // 逆序：从大到小遍历容量
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        // 逆序保证 dp[j-w[i]] 一定来自"上一轮"，不会重复选同一件
    }
}

else{                      // 多重背包（有限数量 s[i]）
    if(s[i] > t / w[i]){   // 如果库存数量 > 容量能装的最大件数
        // 说明永远用不完库存，等价于完全背包 → 正序遍历
        for(int j = w[i]; j <= t; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    else{                  // 库存数量有限 → 拆成 s[i] 个01背包
        for(int k = 1; k <= s[i]; k++){      // 枚举每一件"拆分出来"的物品
            for(int j = t; j >= w[i]; j--) { // 每件按01背包处理，逆序
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
    }
}

cout << dp[t] << '\n';     // 输出容量t时的最大价值

💡 核心对比总结

对比项	01背包	完全背包	多重背包
每件物品数量	1件	无限件	s[i]件
容量遍历方向	逆序（大到小）	正序（小到大）	视情况而定
一维转移方程	`dp[j]=max(dp[j],dp[j-w]+v)`	同上	同上（外层多一层k循环）
逆序/正序的原因	防止同一物品被重复使用	允许同一物品被重复使用	—
时间复杂度	O(n×c)	O(n×c)	O(n×c×s)