多重背包

动态规划

说明

每件物品有数量上限；下例把数量拆成二进制组并做 0/1 背包。

分析

把某类物品的数量拆成 1、2、4 等二进制组和最后的余数，任何不超过上限的件数都能由这些组表示。每组作为一件 0/1 物品倒序更新容量。

图解推演

例如某类上限 5 件，可拆成 1、2、2 三组，每组只能用一次，能表示 0..5 件。组的重量与价值都乘件数，再做倒序 0/1 更新。重复的组大小没有问题，但不能把最后一组仍写成 4，否则会允许选择超过 5 件。

查看图表代码

适用前提与边界

这样比逐件展开更省处理次数，但仍需保证权重和价值乘法不溢出。

示例输入与调用

fmt.Println(BoundedKnapsack([]int{2, 3}, []int{3, 4}, []int{2, 1}, 5))

运行输出

7

完整 Go 示例

package main

import "fmt"

func BoundedKnapsack(weights, values, counts []int, capacity int) int {
	dp := make([]int, capacity+1)
	for i, count := range counts {
		for batch := 1; count > 0; batch *= 2 {
			take := min(batch, count)
			count -= take
			w, v := weights[i]*take, values[i]*take
			for c := capacity; c >= w; c-- {
				dp[c] = max(dp[c], dp[c-w]+v)
			}
		}
	}
	return dp[capacity]
}

func main() {
	fmt.Println(BoundedKnapsack([]int{2, 3}, []int{3, 4}, []int{2, 1}, 5))
}