5.9.2 背包问题

AcWing 网站的题库，除了测试用的「A + B 问题」排在序号上的第一题，最先收录的就是背包问题。站长亲自讲解著名的「背包九讲」的视频题解，是学习背包问题不可错过的优质资源，其 DP 分析法也独树一帜。建议至少掌握「0 - 1背包问题」和「完全背包问题」本文不作多余讲解，只提供风格与本文一致的参考代码。

• 0 - 1 背包

#include <bits/stdc++.h>
using namespace std;
const int N = 1004;
int v[N], w[N];
int dp[N];
int n, m;
int main() {
    cin >> n >> m;
    for (int i=0; i<n; ++i) {
        cin >> v[i] >> w[i];
    }
    for (int i=0; i<n; ++i) {
        for (int j=m; j>=v[i]; --j) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

• 完全背包

#include <bits/stdc++.h>
using namespace std;
const int N = 1004;
int v[N], w[N];
int dp[N];
int n, m;
int main() {
    cin >> n >> m;
    for (int i=0; i<n; ++i) {
        cin >> v[i] >> w[i];
    }
    for (int i=0; i<n; ++i) {
        for (int j=v[i]; j<=m; ++j){
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;
    return 0;
}