完全背包问题

有n个重量和价值分别为wi，vi的物品。从这些物体中挑选出总重量不超过W的物品，求所有方案中价值总和的最大值。在这里，每种物品可以挑选任意多件。

void solve() {
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= W; ++j)
        {
            if (j < w[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
            }
        }
    }
    printf("%d\n", dp[n][W]);
}

对比 01背包

void solve() {
    for (int i = n - 1; i >= 0; i --) {
        for (int j = 0; i < j<= W; ++j) {
            if (j < w[i]) {
                dp[i][j] = dp[i + 1][j];
            } else {
                dp [i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
            }
        }
        
    }
    printf("%d\n", dp[0][W]);
}

则两者的差异只有循环的方向