P54 动态规划 完全背包 内外层 勘误

[Corezcy]

0-1 背包对物品的迭代放在外层,里层的体积或价值逆向遍历;完全背包对物品的迭代放在里层,外层的体积或价值正向遍历

完全背包提供的案例代码好像内外层反了:

int knapsack(vector<int> weights, vector<int> values, int N, int W) {
  vector<int> dp(W + 1, 0);
  for (int i = 1; i <= N; ++i) {
    int w = weights[i - 1], v = values[i - 1];
    for (int j = w; j <= W; ++j) {
      dp[j] = max(dp[j], dp[j - w] + v);
    }
  }
  return dp[W];
}