1. 确定dp数组以及下标的含义#

dp[i][j]：表示从下标为 [0-i] 的物品，每个物品可以取无限次，放进容量为 j 的背包，价值总和最大是多少。

2. 确定递推公式#

• 不放物品 i：背包容量为 j，最大价值为 dp[i-1][j]。
• 放物品 i：背包空出物品 i 的体积 v[i]，剩余容量为 j - v[i]，dp[i][j - v[i]] 表示背包容量 为 j - v[i] 时的最大价值。那么放入物品 i 后的最大价值为：dp[i][j - v[i]] + w[i]。
  • 放入物品 i 后，背包容量为 j - v[i]，但是物品 i 还可以继续放入背包中，因此我们还是在考虑物品 i。

因此递推公式为：

dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i]);

这里与0-1背包的递推公式不同的是：dp[i][j - v[i]] 这里的 i 没有减去1，也就是说物品 i 还可以继续放入背包中。

0 - 1背包的递推公式为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - v[i]] + w[i]);

3. 初始化dp数组#

首先从 dp[i][j] 的定义出发，如果背包容量 j 为0的话，即 dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

状态转移方程中： dp[i][j] = max(dp[i-1][j], dp[i-1][j - v[i]] + w[i]) 可以看出，dp[i][j] 依赖于 dp[i-1][j] 和 dp[i][j - v[i]]。可以看出有一个方向 i 是由 i-1 推导出来，那么 i 为0的时候就一定要初始化。 因此我们需要初始化 dp[0][j]，即当没有物品时，背包的最大价值为0。

dp[0][j]，即：存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

• 那么很明显当 j < v[0] 时，dp[0][j] 应该为0，因为背包容量不够放下物品0。

• 当 j >= v[0] 时，dp[0][j] 应该为 w[0]，因为背包容量足够放下物品0。

j >= v[0] ，dp[0][j] 如果能放下 v[0] 的话，就一直装，每一种物品有无限个。

因此我们可以初始化 dp[0][j] 为：

vector<int> dp(W + 1, 0);
for (int j = 0; j <= W; ++j) {
    if (j >= v[0]) {
        dp[j] = w[0];
    }
}

4. 遍历顺序#

在0 - 1背包中，先遍历物品，再遍历背包容量，或者是先遍历背包容量，再遍历物品，都是可行的，因为这是由推导顺序决定的。

// 先遍历物品，再遍历背包容量
for (int i = 0; i < N; ++i) {
    for (int j = 1; j <= W; ++j) {
        if (j < v[i]) {
            dp[i][j] = dp[i-1][j]; // 背包容量不够放下物品i
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i]); // 放下物品i
        }
    }
}

// 先遍历背包容量，再遍历物品
for (int j = 0; j <= W; ++j) {
    for (int i = 1; i < N; ++i) {
        if (j < v[i]) {
            dp[i][j] = dp[i-1][j]; // 背包容量不够放下物品i
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i]); // 放下物品i
        }
    }
}

5. 整体代码#

vector<int> knapsack(int W, vector<int>& v, vector<int>& w) {
    int N = v.size();
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0)); // dp[i][j]表示从下标为[0-i]的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。
    
    for (int j = 0; j <= W; ++j) {
        if (j >= v[0]) {
            dp[0][j] = w[0];
        }
    }

    for (int i = 1; i < N; ++i) {
        for (int j = 0; j <= W; ++j) {
            if (j < v[i]) {
                dp[i][j] = dp[i-1][j]; // 背包容量不够放下物品i
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i]); // 放下物品i
            }
        }
    }

    return dp[N - 1]; // 返回最后一行，即所有物品的最大价值
}

1. 确定dp数组以及下标的含义#

dp[j]：表示从下标为 [0-N] 的物品，每个物品可以取无限次，放进容量为 j 的背包，价值总和最大是多少。

2. 确定递推公式#

在上面的二维dp表示中，dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i])。

for (int i = 0; i < N; ++i) {
    for (int j = 1; j <= W; ++j) {
        if (j < v[i]) {
            dp[i][j] = dp[i-1][j]; // 背包容量不够放下物品i
        } else {
            dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i]); // 放下物品i
        }
    }
}

将上一层 dp[i-1] 的那一层拷贝到 当前层 dp[i] ，那么 递推公式由：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]) 变成： dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])

所以我们可以将二维dp表示转化为一维dp表示。

dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

• 这里的 j 是从 W 到 v[i] 递减的，表示当前背包容量为 j，如果放入物品 i，那么剩余容量为 j - v[i]。

3. 初始化dp数组#

vector<int> dp(W + 1, 0);

4. 遍历顺序#

在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的，因为 dp[j] 是根据 下标 j 之前所对应的 dp[j] 计算出来的。 只要保证下标j之前的 dp[j] 都是经过计算的就可以了。

// 先遍历物品，再遍历背包容量
for (int i = 0; i < N; ++i) {
    for (int j = v[i]; j <= W; ++j) { // 从v[i]开始遍历
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]); // 放下物品i
    }
}

// 先遍历背包容量，再遍历物品
for (int j = 0; j <= W; ++j) {
    for (int i = 0; i < N; ++i) { // 从0开始遍历
        if (j >= v[i]) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]); // 放下物品i
        }
    }
}