【例86.2】 01背包问题

解题思路

dp[j]表示容量不超过j时最大价值，每物品只选一次。处理重量w价值v时，从M向w倒序更新dp[j]=max(dp[j],dp[j-w]+v)。

正确性说明

任意最优方案分为不选当前物品与选一次两类，对应原dp[j]与上一轮dp[j-w]+v。倒序保证后者仍来自上一轮，取两类最优即正确。

易错点

必须倒序，保证读取上一轮状态，不能重复使用同件。

复杂度

时间O(NM)，空间O(M)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int M, N;
    cin >> M >> N;
    vector<long long> dp(M + 1);
    while (N--) {
        int w;
        long long v;
        cin >> w >> v;
        for (int j = M; j >= w; j--)
            dp[j] = max(dp[j], dp[j - w] + v);
    }
    cout << dp[M] << "\n";
    return 0;
}