完全背包问题

#include <iostream>
#include <algorithm>   // max()函数
using namespace std;

int main() {
    int n = 2;          // 物品数量
    int W = 5;          // 背包最大容量
    int weight[] = {2, 3};   // 每个物品的重量
    int value[] = {3, 4};    // 每个物品的价值

    int dp[6] = {0};    // dp[w] = 容量为w时的最大价值，初始为0

    for (int i = 0; i < n; i++) {          // 遍历每个物品
        for (int w = weight[i]; w <= W; w++) {  // ⚠️ 正序！从小到大！
            // 和01背包唯一的区别就是这里！
            // dp[w]：不选当前物品
            // dp[w-weight[i]] + value[i]：选当前物品（可能选多次）
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }

    cout << "最大价值: " << dp[W] << endl;  // 输出答案
    return 0;
}

// 01背包：内层逆序（从大到小）
for (int i = 0; i < n; i++)
    for (int w = W; w >= weight[i]; w--)   // ← 逆序！
        dp[w] = max(dp[w], dp[w-weight[i]] + value[i]);

// 完全背包：内层正序（从小到大）
for (int i = 0; i < n; i++)
    for (int w = weight[i]; w <= W; w++)   // ← 正序！
        dp[w] = max(dp[w], dp[w-weight[i]] + value[i]);
//        ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
//        除此之外，代码完全一样！