完全背包

完全背包与 0-1 背包差在哪个下标？

• 条件: 每件物品数量不限, 可重复选取;
• 差别: 选入第 i 件后仍可继续选第 i 件, 所以转移来源是本行而不是上一行;
• 方程: dp[i][c] = max(dp[i-1][c], dp[i][c - wgt[i-1]] + val[i-1]);
• 对照: 0-1 背包用 dp[i-1][c - wgt[i-1]], 见 0-1 背包;

const unboundedKnapsackDP = (wgt, val, cap) => {
  const n = wgt.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(cap + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let c = 0; c <= cap; c++) {
      if (wgt[i - 1] > c) dp[i][c] = dp[i - 1][c];
      else dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
    }
  }
  return dp[n][cap];
};

空间优化后为什么改成正序遍历？

• 一维写法: dp[c] = max(dp[c], dp[c - wgt[i-1]] + val[i-1]);
• 正序原因: 需要 dp[c - wgt] 是本行刚更新过的值, 正序遍历保证左列先被本轮刷新;
• 对照: 0-1 背包倒序避免重复选取, 完全背包正序正是为了允许重复选取;
• 复杂度: 时间 O(n * cap), 空间 O(cap);

const unboundedKnapsackDPComp = (wgt, val, cap) => {
  const dp = new Array(cap + 1).fill(0);
  for (let i = 1; i <= wgt.length; i++) {
    for (let c = wgt[i - 1]; c <= cap; c++) {
      dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
    }
  }
  return dp[cap];
};

内层遍历顺序会不会改变问题含义？

• 物品在外、容量在内: 得到的是组合 (不计顺序), 因为按物品顺序一次性决定每件物品的数量;
• 容量在外、物品在内: 得到的是排列 (计顺序), 因为每个容量位置都能重新挑所有物品;
• 判断方法: 问"先选 A 再选 B"和"先选 B 再选 A"是否算同一种方案;
• 应用: 零钱兑换 2 用物品在外求组合数;