0-1背包理论基础.md

什么是0-1背包问题？

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

方法一：二维dp数组

五部曲

1. dp数组：dp[i][j]: 从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少
2. 递推公式：两种情况中取最大值
   1. 取第i个物品：dp[i-1][j-weight(i)] + value(i)
   2. 不取第i个物品：dp[i-1][j]
3. 初始化：
   1. dp[i][0] = 0：容量为零的书包没有任何价值
   2. dp[0][j]当j大于等于weight(0)时 = value(0)
4. 遍历顺序：两种顺序都一样，但先遍历物品再遍历容量更好理解

func bag_problem_2d(weights []int, values []int, volume int) int {
	dp := make([][]int, len(weights))
	for i := range dp {
		dp[i] = make([]int, volume+1)
	}
	// 初始化
	// 这一步可省略，因为数组初始化后本来就是零值
	for i := 0; i < len(weights); i++ {
		dp[i][0] = 0
	}
	for j := weights[0]; j <= volume; j++ {
		dp[0][j] = values[j]
	}

	for i := 1; i < len(weights); i++ {
		for j := 0; j <= volume; j++ {
			if j < weights[i] {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]]+values[i])
			}
		}
	}
	return dp[len(weights)-1][volume]
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

方法二：一维滚动dp数组

五部曲

1. dp数组：dp[j]: 容量为j的背包所背的最大价值
2. 递推公式：两种情况中取最大值
   1. 取第i个物品：dp[j-weight(i)] + value(i)（也就是容量为j的背包，放入物品i了之后的价值）
   2. 不取第i个物品：dp[j]（也就是容量为j的背包，不放入物品i，总价值不变）
3. 初始化： dp[j] = 0：不放入任何物品总价值都为零（假设价值都大于零）
4. 遍历顺序：遍历容量时倒序，因为正序的话会导致同样的物品被重复放入

func bag_problem_1d(weights []int, values []int, volume int) int {
	dp := make([]int, volume+1)
	for i := 0; i < len(weights); i++ {
		for j := volume; j >= weights[i]; j-- {
			dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
		}
	}
	return dp[volume]
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}