0/1 背包

动态规划

说明

每件物品最多选一次；容量从大到小更新，防止重复使用同一件。

分析

dp[c] 表示容量不超过 c 时能得到的最大价值。处理某件物品时从大容量倒序更新，确保右侧读取的是“未用过当前物品”的旧状态。

图解推演

容量 5、物品 (重2,值3) 与 (重3,值4) 可合得价值 7。处理第一件时，必须先算 dp[4] 再算 dp[2]，读取的 dp[2] 还是旧值 0；若正序先把 dp[2] 改为 3，随后 dp[4] 会错误得到 6，把仅有一件的物品拿了两次。

查看图表代码

适用前提与边界

若正序更新，同一件物品可能在同轮被选多次，题意就变成完全背包。

示例输入与调用

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

运行输出

7

完整 Go 示例

package main

import "fmt"

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

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