完全背包模板

#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];

    // 完全背包：正序遍历容量
    int dp[MAXW] = {};
    for (int i = 0; i < n; i++)
        for (int j = w[i]; j <= W; j++)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

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

📖 要点说明

• 与01背包唯一区别：容量正序遍历
• 正序保证同一物品可被多次选择
• 时间 O(nW)

⚠️ 常见错误

• 写成倒序变成01背包
• 完全背包和01背包混用
• 求方案数时 max 改为 +=