01背包模板

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

const int MAXW = 10010;

int main() {
    int n, W;
    cin >> n >> W;
    int w[n], v[n];
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];

    // 二维写法
    // dp[i][j] = 前 i 个物品，容量 j 的最大价值
    // for i: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

    // 一维优化（倒序遍历容量）
    int dp[MAXW] = {};
    for (int i = 0; i < n; i++)
        for (int j = W; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

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

📖 要点说明

• 01背包：每件物品最多选一次
• 一维优化：容量倒序遍历，避免重复选
• 状态转移：dp[j] = max(不选, 选)

⚠️ 常见错误

• 一维正序遍历变成完全背包
• 容量遍历范围写错（j < w[i] 不用更新）
• 忘初始化 dp 数组