c++DP：01 背包（0/1 Knapsack）

✅ 功能说明

每件物品只有一次选择机会，求最大价值。

✅ 代码模板

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, W;
    cin >> n >> W;  // n = 物品数量, W = 背包容量

    vector<int> weight(n+1), value(n+1);

    // 读入每件物品的重量与价值
    for(int i=1; i<=n; i++){
        cin >> weight[i] >> value[i];
    }

    // dp[j] 表示容量为 j 时能获得的最大价值
    vector<int> dp(W+1, 0);

    // 01 背包：容量必须从大到小更新，确保每物品只使用一次
    for(int i=1; i<=n; i++){
        for(int j=W; j>=weight[i]; j--){
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    cout << dp[W] << "\n";   // 输出最大价值
    return 0;
}

✅ 输入样例

4 5
1 2
2 4
3 4
4 5

含义

✅ 输出样例

8

最优方案

选择重量 1 + 2 + 3，价值 2 + 4 + 4 = 10
但容量仅 5
选择 2 + 3 → 4 + 4 = 8
最佳值 = 8