完全背包

动态规划

说明

每件物品可重复选择；容量从小到大更新以允许同轮再次使用。

分析

与 0/1 背包不同，每类物品可无限次选择。容量正序更新时，dp[c−w] 可能已经包含当前物品，所以可以在同轮再次使用它。

图解推演

只看重量 2、价值 3 这一类：容量由小到大更新，dp[2]=3、dp[4]=6、dp[6]=9，后一步有意读取本轮新状态。正文另有重量 3、价值 4，容量 6 时仍是三件重量 2 的物品更优。这里允许剩余容量，所以全零初始化合法；恰好装满需额外区分不可达状态。

查看图表代码

适用前提与边界

权重必须为正；零重量且正价值的物品会让最优值无界。

示例输入与调用

fmt.Println(UnboundedKnapsack([]int{2, 3}, []int{3, 4}, 6))

运行输出

9

完整 Go 示例

package main

import "fmt"

func UnboundedKnapsack(weights, values []int, capacity int) int {
	dp := make([]int, capacity+1)
	for i, w := range weights {
		for c := w; c <= capacity; c++ {
			dp[c] = max(dp[c], dp[c-w]+values[i])
		}
	}
	return dp[capacity]
}

func main() {
	fmt.Println(UnboundedKnapsack([]int{2, 3}, []int{3, 4}, 6))
}