背包问题

问题类型	核心区别	时间复杂度	典型应用场景
0-1背包	物品唯一	O(NV)	单次采购决策
完全背包	物品无限	O(NV)	货币组合问题
多重背包	物品数量限制	O(NVlog⁡S)	资源有限分配
混合背包	物品数量不固定
二维费用背包	双重约束	O(NMK)	多维度资源优化
分组背包	组内互斥	O(NV)	品牌选择问题
有依赖的背包	主件附件依赖	O($$NV^2$$)	组合商品购买
求背包方案数
求背包具体方案数

0/1背包

二维

核心逻辑：

• 二维数组存储状态，dp[i][j]表示前i个物品在容量j时的最大价值
• 时间/空间复杂度：O(n*m)
• 特点：直观体现状态转移过程

#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];       // 价值数组和重量数组
int dp[N][N];         // 二维DP数组
int n, m;             // 物品数量，背包容量

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i-1][j];  // 不选当前物品
            if (j >= w[i])          // 背包能装下时
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
        }
    
    cout << dp[n][m];
    return 0;
}

01背包：滚动数组优化版

优化亮点：

• 空间复杂度降为O(m)
• 关键点：逆序更新避免重复选取物品
• 状态转移方程压缩到一维数组

#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N];
int dp[N];  // 一维DP数组优化空间

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        cin >> w[i] >> v[i];
    
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= w[i]; j--)  // 逆向遍历防止覆盖
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    
    cout << dp[m];
    return 0;
}

倒序的缘故，那么接下来枚举的j都要比先前的j要来的小，当某个位置更新数据时，并不会调用其位置后面的数据，一定会是先调用其位置之前的旧数据， 然后再将当前位置的旧数据覆盖，也就保证了数据更新的有效性。

vector<int> weight = {1, 3, 4};	  // 物品重量
vector<int> value = {15, 20, 30}; // 物品价值
int bag = 4;					  // 背包容量

// 因为01背包遍历背包时是倒序，如果先遍历背包，那么每个dp[j]就只会放入一个物品,结果如下所示：
// 	4 : 15        4 : 20        4 : 30
//  3 : 15        3 : 20
//  2 : 15
//  1 : 15

完全背包

问题特性：

• 物品可无限次选取

• 效率瓶颈：O(n*m)时间复杂度

• 正序关键：允许同一物品多次选取，通过覆盖式更新实现

• 在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的

输入样例：

 3 5
1 2  // 物品1（体积1，价值2）
2 3  // 物品2（体积2，价值3）
3 4  // 物品3（体积3，价值4）

输出结果：

10

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;   // 最大物品数
int v[N], w[N];       // v:体积数组 w:价值数组
int dp[N];            // 一维状态压缩数组

int main() {
    int n, m;         // n:物品数量 m:背包容量
    cin >> n >> m;
    
    // 输入物品参数
    for (int i = 1; i <= n; ++i) 
        cin >> v[i] >> w[i];
    
    memset(dp, 0, sizeof dp);  // 初始化价值为0
    
    // 动态规划主体
    for (int i = 1; i <= n; ++i) 
        for (int j = v[i]; j <= m; ++j)  // 正序遍历实现无限取用
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    
    cout << dp[m];
    return 0;
}

多重背包

核心改进：

• 增加物品数量限制s[i]
• 选取次数k受两个条件约束：k <= s[i]和k*v[i] <= j

#include<iostream>
using namespace std;
const int N = 110;
int v[N], w[N], s[N];  // 新增物品数量限制数组
int dp[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        cin >> v[i] >> w[i] >> s[i];
    
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            for(int k=0; k<=s[i] && k*v[i]<=j; k++) // 受s[i]限制,s[i]过大，导致运算量变大
                dp[i][j] = max(dp[i][j], 
                             dp[i-1][j-k*v[i]] + k*w[i]);
    
    cout << dp[n][m];
    return 0;
}

多重背包：二进制优化版

#include<iostream>
#include<vector>
using namespace std;

struct Good { int v, w; };
const int N = 25000;  // 注意扩容
vector<Good> goods;
int dp[N];

int main() {
    int n, m;
    cin >> n >> m;
    
    // 二进制拆分
    for(int i=0; i<n; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for(int k=1; k<=s; k*=2) {  // 按2的幂次拆分
            s -= k;
            goods.push_back({k*v, k*w});
        }
        if(s>0) goods.push_back({s*v, s*w});//剩余的
    }
    
    // 转化为01背包问题
    for(auto good : goods)
        for(int j=m; j>=good.v; j--)
            dp[j] = max(dp[j], dp[j-good.v] + good.w);
    
    cout << dp[m];
    return 0;
}

优化原理：

• 将数量s分解为1+2+4+…+剩余值，组合可表示任意数量
• 时间复杂度从O(n*m*s)降为O(n*m*log s)
• 空间换时间的典型优化策略

混合背包

#include <iostream>
#include <vector>
using namespace std;

struct Item {
    int weight;  // 物品体积
    int value;   // 物品价值
};

vector<Item> convertItems(int m) {
    vector<Item> items;
    int n, type;
    cin >> n;  // 原始物品数量
    
    while (n--) {
        int w, v, s;
        cin >> w >> v >> s;

        // 类型转换处理
        if (s == -1) {        // 01背包 -> 直接保留
            items.push_back({w, v});
        } 
        else if (s == 0) {    // 完全背包 -> 转为多重背包
            s = m / w;        // 最大可选次数
            for (int k=1; k<=s; k*=2) {  // 二进制分解
                items.push_back({k*w, k*v});
                s -= k;
            }
            if (s > 0) items.push_back({s*w, s*v});
        } 
        else {                // 多重背包 -> 二进制分解
            for (int k=1; k<=s; k*=2) {
                items.push_back({k*w, k*v});
                s -= k;
            }
            if (s > 0) items.push_back({s*w, s*v});
        }
    }
    return items;
}

int main() {
    int m;  // 背包容量
    cin >> m;
    
    vector<Item> items = convertItems(m);
    vector<int> dp(m + 1, 0);

    // 统一按01背包处理
    for (auto& item : items) {
        for (int j = m; j >= item.weight; j--) {
            if (dp[j] < dp[j - item.weight] + item.value) {
                dp[j] = dp[j - item.weight] + item.value;
            }
        }
    }

    cout << "最大价值: " << dp[m] << endl;
    return 0;
}

二维费用背包

又叫双约束背包

#include<iostream>
using namespace std;

const int N = 1e3 + 10, M1 = 1e2 + 10, M2 = 1e2 + 10;
int w[N], c[N];  // w[物品][双维度费用]，c[物品价值]
int dp[M1][M2];  // 状态：容量1≤j1且容量2≤j2时的最小代价

int main() {
    int n, m1, m2; 
    cin >> m1 >> m2 >> n;
    
    // 注意：此处应为cin >> w[i] >> c[i]，原代码存在笔误
    for(int i=1; i<=n; i++) 
        cin >> w[i] >> c[i];  // 修正后的输入
    
    memset(dp, 0x3f, sizeof dp);  // 初始化为无穷大（求最小代价）
    dp = 0;  // 基础状态：0容量0代价
    
    for(int i=1; i<=n; i++)
        for(int j=m1; j>=w[i]; j--)  // 维度1逆向遍历
            for(int k=m2; k>=c[i]; k--)  // 维度2逆向遍历
                dp[j][k] = min(dp[j][k], 
                             dp[j-w[i]][k-c[i]] + 1);  // 假设代价为1
    
    cout << dp[m1][m2];
    return 0;
}

核心逻辑：

1. 双维度逆向遍历保证物品只选一次
2. dp[j][k]表示满足容量j和k时的最小代价
3. 适用场景：无人机送货（重量+体积双限制）

分组背包

实现特点：

1. 三层嵌套循环结构
   • 外层：组别遍历
   • 中层：容量逆向扫描
   • 内层：组内物品决策
2. 关键限制：每组最多选1个物品
3. 典型应用：电商平台同品牌商品选择

#include<iostream>
#include<vector>
using namespace std;

const int N=1e4+10, M=2e2+10, T=1e2+10;
int w[N],c[N];          // 物品重量与价值
vector<int> group[N];   // 分组容器
int dp[M];              // 压缩状态数组

int main(){
    int m,n,t; 
    cin>>m>>n>>t;//容量 物品个数 组数
    
    for(int i=1;i<=n;i++){
        int p;  // 分组号
        cin>>w[i]>>c[i]>>p;
        group[p].push_back(i);  // 按组存储物品索引
    }
    
    for(int g=1;g<=t;g++)               // 遍历所有组
        for(int j=m;j>=0;j--)           // 逆向容量遍历
            for(int k:group[g])         // 遍历组内物品
                if(j>=w[k])             // 容量足够时更新
                    dp[j]=max(dp[j], dp[j-w[k]]+c[k]);
    
    cout<<dp[m];
    return 0;
}

有依赖背包（主附件）

问题描述

在有依赖背包问题中，物品被分为主件和附件两种类型。每个附件只能在其对应的主件被选择的情况下才能被选择。目标是在背包容量的限制下，选择合适的物品（主件及其附件的组合），使得总价值最大化。

假设背包容量为 V，总共有 n 件物品，每件物品要么是主件，要么是附件，每件物品有对应的重量 w[i] 和价值 v[i]。

输入输出示例

输入示例：

 10 5
8 4 0
2 1 1
3 1 1
4 2 0
5 3 4

• 第一行：背包容量 V = 10，物品数量 n = 5。
• 接下来的 n 行：每行包含三个整数 v[i]（价值）、w[i]（重量）、p[i]（依赖关系）。如果 p[i] = 0，表示该物品是主件；否则，表示该物品依赖于编号为 p[i] 的主件。

输出示例：

15

• 输出一个整数，表示在给定背包容量下能获得的最大价值。

C++ 代码实现

Cpp#include <iostream>
#include <cstring>
using namespace std;

const int N = 610;  // 物品数量 (主件数量 + 附件数量)
const int M = 1010;  // 背包容量

// 主件及其附件信息
struct Item {
    int v, w;  // 价值和重量
};

Item master[N], accessory1[N], accessory2[N];  // 主件、每个主件的第一个附件、每个主件的第二个附件
int n, m;  // 物品数量和背包容量
int dp[M];

int main() {
    cin >> m >> n;
    int cnt = 0;  // 记录主件数量
    for (int i = 1; i <= n; i++) {
        int v, w, p;
        cin >> v >> w >> p;
        if (p == 0) {  // 主件
            master[++cnt] = {v, w};
        } else {  // 附件
            if (!accessory1[p].v) {  // 第一个附件
                accessory1[p] = {v, w};
            } else {  // 第二个附件
                accessory2[p] = {v, w};
            }
        }
    }
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= cnt; i++) {  // 遍历每个主件
        for (int j = m; j >= master[i].w; j--) {  // 遍历背包容量
            int val = dp[j - master[i].w] + master[i].v;
            // 情况1: 只选主件
            dp[j] = max(dp[j], val);
            // 情况2: 选主件和第一个附件
            if (j >= master[i].w + accessory1[i].w) {
                val = dp[j - master[i].w - accessory1[i].w] + master[i].v + accessory1[i].v;
                dp[j] = max(dp[j], val);
            }
            // 情况3: 选主件和第二个附件
            if (j >= master[i].w + accessory2[i].w) {
                val = dp[j - master[i].w - accessory2[i].w] + master[i].v + accessory2[i].v;
                dp[j] = max(dp[j], val);
            }
            // 情况4: 选主件和两个附件
            if (j >= master[i].w + accessory1[i].w + accessory2[i].w) {
                val = dp[j - master[i].w - accessory1[i].w - accessory2[i].w] + master[i].v + accessory1[i].v + accessory2[i].v;
                dp[j] = max(dp[j], val);
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}

1. 四重组合决策：
   • 单独主件
   • 主件+附件A
   • 主件+附件B
   • 主件+双附件
2. 实际应用：电脑配置（主板+可选配件）

求背包问题的方案数

求解用给定物品装满背包的不同组合方式总数。

dp[j] = 不选该物品的方案数 + 选该物品的方案数

#include <iostream>
#include <cstring> // 用于memset初始化
using namespace std;

const int N = 1010, M = 1010;
int w[N];  // 物品重量数组
int dp[M]; // dp[j]表示容量j的背包恰好装满的方案数

int main() {
    int n, m;
    cin >> n >> m;

    // 读取物品重量（从1开始存储）
    for (int i = 1; i <= n; i++) 
        cin >> w[i];

    // 初始化dp数组
    memset(dp, 0, sizeof(dp)); // 全部初始化为0
    dp[0] = 1;                 // 容量0时方案数为1（空包）

    // 完全背包动态规划
    for (int i = 1; i <= n; i++) {           // 遍历每个物品
        for (int j = w[i]; j <= m; j++) {    // 正序遍历容量(完全背包)
            dp[j] += dp[j - w[i]];           // 累加方案数
        }
    }

    cout << dp[m] << endl;
    return 0;
}

背包的具体方案数

01背包的具体方案数

不仅能计算最大价值，还能回溯输出具体选择的物品方案。

//假设01背包dp数组已经填充完成
vector<int> res;
for (int i = n, j = m; i >= 1; i--) {//逆向遍历：从最后一个物品开始倒推，判断是否选择了该物品。
    if (j >= w[i] && dp[i][j] == dp[i-1][j-w[i]] + c[i]) {//若当前容量足够且选择物品i后的价值等于dp[i][j]，则说明物品i被选中。
        res.push_back(i);  // 记录选择的物品编号
        j -= w[i];         // 扣减背包容量
    }
}

示例：

输入：
5 3    // 背包容量5，3个物品
2 3    // 物品1：重量2，价值3
3 4    // 物品2：重量3，价值4
4 5    // 物品3：重量4，价值5

输出：
2 1    // 选择物品2和1，总重量5，总价值7

解释：

• 最大价值为7（物品2价值4 + 物品1价值3）。
• 回溯时会优先检测到物品2被选中

完全背包的具体方案

• 特点：每物品可选无限次。

• 调整思路

  • 回溯步骤

      // 动态规划（一维优化）
        for (int i = 1; i <= n; ++i) {
            for (int j = w[i]; j <= m; ++j) { // 正序遍历
                if (dp[j - w[i]] + v[i] > dp[j]) {
                    dp[j] = dp[j - w[i]] + v[i];
                    cnt[i][j] = cnt[i][j - w[i]] + 1; // 累加选取次数
                }
            }
        }
    
        // 回溯具体方案
        vector<int> res;
        for (int i = n, j = m; i > 0; --i) {
            while (cnt[i][j] > 0) {
                res.push_back(i);
                j -= w[i];
                cnt[i][j]--; // 递减次数
            }
        }
    
        // 输出方案（正序）
        for (int item : res) 
            cout << item << " ";
        cout << endl;
        
        return 0;
    }

• 要点：需循环检查同一物品被选取的次数。