背包 DPCSP-S

💡 核心思想

背包问题是动态规划的经典模型：给定容量为 W 的背包和 n 个物品（各有重量和价值），如何选择使总价值最大。01背包（每个物品最多选一个）、完全背包（物品可重复选）、多重背包（物品有数量限制）是三种基本变体。

🎯 直觉理解

想象你有一个承重10kg的背包去超市"抢购"。每样商品有重量和价格，你只能拿一次（01背包）。你要做出取舍：拿了这个重的东西，就得放弃其他轻的组合。动态规划就是在每个容量值上都算出"最优选择"。

📝 算法流程

1. 定义状态：$dp[j]$ = 容量为 $j$ 时的最大价值
2. 01背包：$dp[j] = \max(dp[j], dp[j-w_i] + v_i)$，j 逆序
3. 完全背包：同上但 j 正序
4. 多重背包：二进制拆分优化

$$dp[j] = \max_{i} (dp[j], dp[j-w_i] + v_i)$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, W; cin >> W >> n;
    vector<long long> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        int w, v; cin >> w >> v;
        for (int j = W; j >= w; j--) // 01背包：逆序
            dp[j] = max(dp[j], dp[j-w] + (long long)v);
    }
    cout << dp[W] << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目