多重背包问题

多重背包问题

• 第 i 种物品最多有 n[i] 件可用

朴素思维

• 把 n[i] 个 i 种物品分为 n 份，对着 n 份物品看做 01 背包问题解决
• 例如有 n 个 a 物品，就把他们分为 a1、a2、a3... an，然后用 01 背包解决
• 在 01 背包代码的基础上，添加 第三个 for 循环 k
  • 循环退出条件为 k <= n[i] 小于物品数目
  • 且 k * w[i] <= j 当前剩余容量放得下

多重背包问题

for (int i = 1; i <= n; i++) {

for (int j = m; j >=0; j--) {

for (int k = 1; k <= nums[i] && k * w[i] <= j; k++) {

dp[j] = Math.max(dp[j], dp[j - k * w[i]] + k * v[i]);

}

}

}

多重背包的二进制优化

引例：有 1000 个苹果，10 个箱子，要想不论拿多少个苹果，都能成箱成箱的拿，应该如何放置

• 按照二进制设置
• 第一个箱子放 1，第二个箱子放2，第三个箱子放4，第四个箱子放8...
• 那么总是成箱成箱的拿，因为二进制能表示任何自然数