多重分组与二维背包

多重背包如何转化为 0-1 背包？

• 条件: 第 i 件物品最多选 count[i] 件;
• 做法: 在 0-1 背包内侧再枚举选择件数 k (0 <= k <= count[i]);
• 方程: dp[i][c] = max(dp[i-1][c], dp[i-1][c - k * wgt[i-1]] + k * val[i-1]);
• 约束: k * wgt[i-1] <= c 才允许放入;
• 复杂度: 时间 O(n * cap * maxCount);

const multiKnapsackDP = (wgt, val, count, 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++) {
      for (let k = 0; k <= count[i - 1] && k * wgt[i - 1] <= c; k++) {
        dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - k * wgt[i - 1]] + k * val[i - 1]);
      }
    }
  }
  return dp[n][cap];
};

• 空间优化: 压缩为一维后按 0-1 背包倒序遍历, 见 0-1 背包;

分组背包如何保证每组只选一个？

• 条件: 物品分成 n 组, 第 i 组有 groupCount[i] 个物品, 每组最多选一个;
• 状态: dp[i][c] 为前 i 组在容量 c 下的最大价值;
• 方程: 不选该组用 dp[i-1][c]; 选该组第 j 个用 dp[i-1][c - wgt[i-1][j]] + val[i-1][j];
• 关键: 组内遍历 j 时取最大值, 而不是像多重背包那样累加件数, 从而天然互斥;

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

二维背包如何增加一个容量维度？

• 条件: 除重量 cap 外还有容量 vol 上限, 每件物品同时占用 wgt[i] 与 volume[i];
• 状态: dp[i][c][v] 为前 i 件物品在重量 c、容量 v 下的最大价值;
• 方程: dp[i][c][v] = max(dp[i-1][c][v], dp[i-1][c - wgt[i-1]][v - vol[i-1]] + val[i-1]);
• 初值: 任一维为 0 时价值为 0;
• 答案: dp[n][cap][vol];
• 空间优化: 压缩为二维数组, 两个维度都倒序遍历;

混合背包怎么处理？

• 条件: 同一批物品里 count[i] 为 0 表示无限件, 为 1 表示只选一次, 为其它正整数表示限量;
• 做法: 逐物品判断类型, 分别套用完全背包或 0-1 背包或多重背包的循环写法;
• 注意: 完全背包正序遍历, 其余倒序遍历, 同一份一维数组可以复用;