什么是背包问题

背包问题（Knapsack Problem）是经典的组合优化问题，也是动态规划中的经典模型。问题描述为：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择物品使得总价值最大。

主要类型

01背包

每种物品只有一件，可以选择放或不放。

状态定义

dp[i][j]：前i件物品放入容量为j的背包中能获得的最大价值

转移方程

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

空间优化（滚动数组）

vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; i++) {
    for (int j = capacity; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

示例代码

// 01背包问题
int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // 必须从后往前遍历，防止物品被重复使用
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    
    return dp[capacity];
}

完全背包

每种物品有无限件，可以取任意多件。

状态定义

dp[j]：容量为j的背包能获得的最大价值

转移方程

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

空间优化

vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; i++) {
    for (int j = w[i]; j <= capacity; j++) {  // 从前向后遍历
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

示例代码

// 完全背包问题
int knapsackComplete(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // 从前向后遍历，允许物品重复使用
        for (int j = weights[i]; j <= capacity; j++) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    
    return dp[capacity];
}

多重背包

每种物品有限定的数量。

二进制优化

// 将多重背包转化为01背包
vector<pair<int, int>> items;  // (weight, value)
for (int i = 0; i < n; i++) {
    int cnt = nums[i];
    int k = 1;
    while (k <= cnt) {
        items.push_back({weights[i] * k, values[i] * k});
        cnt -= k;
        k <<= 1;
    }
    if (cnt > 0) {
        items.push_back({weights[i] * cnt, values[i] * cnt});
    }
}
// 然后使用01背包求解

典型例题

1. 01背包基础

[P1048 [NOIP2005 普及组] 采药](https://www.luogu.com.cn/problem/P1048)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T, M;
    cin >> T >> M;
    vector<int> time(M), value(M);
    for (int i = 0; i < M; i++) {
        cin >> time[i] >> value[i];
    }
    
    vector<int> dp(T + 1, 0);
    for (int i = 0; i < M; i++) {
        for (int j = T; j >= time[i]; j--) {
            dp[j] = max(dp[j], dp[j - time[i]] + value[i]);
        }
    }
    
    cout << dp[T] << endl;
    return 0;
}

2. 完全背包基础

P1616 疯狂的采药

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int T, M;
    cin >> T >> M;
    vector<int> time(M), value(M);
    for (int i = 0; i < M; i++) {
        cin >> time[i] >> value[i];
    }
    
    vector<ll> dp(T + 1, 0);  // 注意使用long long防止溢出
    for (int i = 0; i < M; i++) {
        for (int j = time[i]; j <= T; j++) {
            dp[j] = max(dp[j], dp[j - time[i]] + (ll)value[i]);
        }
    }
    
    cout << dp[T] << endl;
    return 0;
}

常见变体

1. 恰好装满

// 初始化dp[0] = 0, 其他为-INF
vector<int> dp(capacity + 1, -INF);
dp[0] = 0;

2. 方案数统计

// 求恰好装满背包的方案数
vector<int> dp(capacity + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = capacity; j >= weights[i]; j--) {
        dp[j] += dp[j - weights[i]];
    }
}

3. 最优方案记录

vector<int> dp(capacity + 1, 0);
vector<vector<bool>> choice(n, vector<bool>(capacity + 1, false));

for (int i = 0; i < n; i++) {
    for (int j = capacity; j >= weights[i]; j--) {
        if (dp[j] < dp[j - weights[i]] + values[i]) {
            dp[j] = dp[j - weights[i]] + values[i];
            choice[i][j] = true;
        }
    }
}

// 回溯输出方案
int j = capacity;
for (int i = n - 1; i >= 0; i--) {
    if (choice[i][j]) {
        cout << i << " ";
        j -= weights[i];
    }
}

总结

实战技巧

1. 空间优化：一维数组实现时，注意遍历顺序
2. 初始化技巧：根据问题要求选择合适的初始值
3. 边界处理：注意数组越界问题
4. 类型选择：根据题目描述判断背包类型
5. 复杂度分析：确保算法在时间和空间上可行

扩展阅读

1. 混合背包：同时包含01背包、完全背包和多重背包
2. 二维费用背包：物品有两个维度的费用
3. 分组背包：物品分组，每组只能选一个
4. 依赖背包：物品间存在依赖关系
5. 泛化物品：价值随费用