背包问题

题解

背包问题

一类精巧的动态规划

问题雏形, 01背包

有 N 件物品，一个容量为 C 的背包。
第i件物品的重量是 W[i], 价值是 V[i]。
在不超过背包容量的情况下，怎么装物品使得装入的总价值最大？求出最大总价值。

分析

看一个具体的例子：

假设背包的大小是 10，有 4 个物品，
体积分别是 [2,3,5,7]，
价值分别是 [2,5,2,5]。

1、如果仅考虑将前一个物品放入背包，只要背包容量大于2，都可以获取价值为2的最大价值

表格首列为物品编号+(物品体积，物品价值）

物品\容量	0	1	2	3	4	5	6	7	8	9	10
1 (2,2)	0	0	2	2	2	2	2	2	2	2	2
2 (3,5)
3 (5,2)
4 (7,5)

2、现在考虑仅将前两个物品放入背包, 如果背包容量不小于5就可以把两个物品都放入，获得价值2+5=7; 如果不能全部放入，就需要选择体积不超，价值最大的物品

物品\容量	0	1	2	3	4	5	6	7	8	9	10
1 (2,2)	0	0	2	2	2	2	2	2	2	2	2
2 (3,5)	0	0	2	5	5	7	7	7	7	7	7
3 (5,2)
4 (7,5)

3、同理，考虑仅将前三个物品放入背包

物品\容量	0	1	2	3	4	5	6	7	8	9	10
1 (2,2)	0	0	2	2	2	2	2	2	2	2	2
2 (3,5)	0	0	2	5	5	7	7	7	7	7	7
3 (5,2)	0	0	2	5	5	7	7	7	7	7	9
4 (7,5)

4、现在考虑将全部四个物品放入背包，可以依据前三个物品放入的结果来制定方案

物品\容量	2	3	4	5	6	7	8	9	10
1 (2,2)	2	2	2	2	2	2	2	2	2
2 (3,5)	2	5	5	7	7	7	7	7	7
3 (5,2)	2	5	5	7	7	7	7	7	9
4 (7,5)	2	5	5	7	7	7	7	7	10

不难发现，前n个物品在背包容量为c的情况下能得到的最大价值f(n, c)，可以依赖前n-1个物品的情况来得到：

1. 如果背包总容量小于 W[n]，不能装第n个物品，得到的价值是 f(n-1, c)
2. 装第 n 个物品，得到的价值是  f(n-1, c-W[n]) + V[n]
即使第 n 个物品可以装，得到的结果也不一定比不装好，
所以 f(n,v) = max(f(n-1, v), f(n-1, c-W[n]) + V[n])

动态规划

在物品数量和背包容量两个状态上实施动态规划即可；
定义 dp[i][j] 表示 将前 i 个物品放入容量为 j 的背包里所获得的最大价值

递推关系：dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]]+V[i])
初始状态：dp[i][0] = 0

初始实现

为了好处理边界，dp数组可以申请为(n+1) * (C+1)

func zeroOnePack(C int, W, V []int) int {
	if C <= 0 || len(W) != len(V) {
		return 0
	}
	n := len(W)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, C+1)
	}
	for i := 1; i <= n; i++ { // 遍历物品
		for j := W[i-1]; j <= C; j++ { // 遍历背包容量
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i-1]]+V[i-1])
		}
	}
	return dp[n][C]
}

空间优化

dp[i][...] 只依赖于 dp[i - 1][...], dp数组可以降维; 降维后容量需要从后往前遍历，以保证子问题用到的数据不被覆盖——再回想一下填表过程就能明白。

func zeroOnePack(C int, W, V []int) int {
	if C <= 0 || len(W) != len(V) {
		return 0
	}
	n := len(W)
	dp := make([]int, C+1)
	for i := 0; i < n; i++ {
		// 需要逆向，如果正向，会变成完全背包问题
		for j := C; j >= W[i]; j-- {
			dp[j] = max(dp[j], dp[j-W[i]]+V[i])
		}
	}
	return dp[C]
}

完全背包

上面讨论的问题，物品只能被选中 1 次或 0 次，因此称为 01 背包问题。
还有一类问题，物品可被选中 多次 或 0 次，每种物品都有无限件可用，称为 完全背包问题。
解法类似，都是动态规划。略有不同，将01背包一维dp的解法稍作修改，内层循环即遍历容量时从前向后遍历即可：

01背包中之所以逆向，是为了 max 里的两项为前一状态的值，防止过早覆盖，所以逆序；
完全背包中，正序写，则max里的两项是当前状态的值。

对应二维dp   dp[i][j] = max(dp[i][j], dp[i][j-W[i-1]]+V[i-1])
01背包则是   dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i-1]]+V[i-1])

func completePack(C int, W, V []int) int {
	if C < 0 || len(W) != len(V) {
		return 0
	}
	n := len(W)
	dp := make([]int, C+1)
	for i := 0; i < n; i++ {
		for j := W[i]; j <= C; j++ {
			dp[j] = max(dp[j], dp[j-W[i]]+V[i])
		}
	}
	return dp[C]
}

多重背包问题

多重背包问题限定了一种物品的个数，解决多重背包问题，只需要把它转化为0-1背包问题即可。
比如，有2件价值为5，重量为2的同一物品，就可以分为物品a和物品b，a和b的价值都为5，重量都为2。
如果同一种物品有多个，可以用二进制优化；比如有 x 个，可以分成 1、2、4、。。。、rest 这样的物品
(1、2、4、。。。、rest, 可以凑出 [1, x]内的所有数字)

示例代码如下：

type Good struct {
	v, w int
}

func main() {
	var n, v int
	_, _ = fmt.Scanf("%d %d", &n, &v)
	var goods []Good
	for i := 0; i < n; i++ {
		var v, w, s int
		_, _ = fmt.Scanf("%d %d %d", &v, &w, &s)
		for k := 1; k <= s; k *= 2 {
			s -= k
			goods = append(goods, Good{v: v * k, w: w * k})
		}
		if s > 0 {
			goods = append(goods, Good{v: v * s, w: w * s})
		}
	}
	fmt.Println(pack(goods, v))
}

func pack(goods []Good, v int) int {
	dp := make([]int, v+1)
	for _, good := range goods {
		for c := v; c >= good.v; c-- {
			dp[c] = max(dp[c], dp[c-good.v]+good.w)
		}
	}
	return dp[v]
}

还可以利用单调队列对多重背包问题优化，略。

初始化细节

有的问题求“恰好装满背包”的最优解，有的问题不要求把背包装满。

对于“恰好装满”的问题，在初始化时，dp[0] 还是 0，但是其他元素需要是 -∞

第二种问题，即不要求必须恰好装满背包，初始化所有元素为 0 就行。

可以这样理解：
初始化的 dp 数组事实上就是在没有任何物品可以放入背包时的合法状态。
如果要求背包恰好装满，那么此时只有容量为 0 的背包可能被价值为 0 的虚拟物品“恰好装满“，其他容量的背包均没有合法解，属于未定义的状态，
再结合状态转移方程，它们的值就都应该是 -∞ 。
如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0。