完全背包问题

与01背包的区别：

01背包中每件物品只能拿一次，而完全背包中的物品可以拿无限次。

代码上的区别

前者的二层循环是逆序，而后者则是顺序

01

顺序

朴素解法，暴力三重循环:

#include<iostream>

using namespace std;
//朴素暴力版本，三重循环

const int N = 1010;
int dp[N][N];
int w[N];
int v[N];

int main() {
    int n, weight;
    scanf("%d%d", &n, &weight);

    for (int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= weight; j++)
            for (int k = 1; k * w[j] <= j; k++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[j]] + k * v[j]);
    printf("%d\n", dp[n][weight]);
}

优化解法：

#include<iostream>

using namespace std;

const int N = 10000;
int v[N];    // 体积
int w[N];    // 价值
int f[N][N];  // f[i][j], j体积下前i个物品的最大价值

int main() {
    int n, m;  // 背包体积
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];  // 不选第i个物品
            if (j >= v[i])           // 可以选择第i个物品，状态方程见上面推导
                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    printf("%d\n", f[n][m]);
    return 0;
}