0005

5. 多重背包问题 II

题目

有 $N$ 种物品和一个容量是 $V$ 的背包。

第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $v_i, w_i, s_i$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \lt N \le 1000$

$0 \lt V \le 2000$

$0 \lt v_i, w_i, s_i \le 2000$

提示：

本题考查多重背包的二进制优化方法。

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

题解

前置题目：0004

前置知识：01背包

本题知识：动态规划-背包问题

题目分析

本题和完全背包问题的区别只有每件物品的数量是有限的。

根据题目要求可知暴力算法三重循环处理的数据规模是 40 亿。在我的 2核4G ubuntu 上测试，1s内cpp可以处理1亿次运算，go可以处理10亿次运算。go使用暴力算法实际测试可以 ac 的，cpp就不行了会 TLE。

优化思路一：是否可以通过递推关系从三重循环优化成二重循环

f(i, j ) = Max( f(i-1,j) , f(i-1,j-v)+w ,  f(i-1,j-2*v)+2*w , ..... , f(i-1,j-s*v)+s*w )
f(i, j-v)= Max(            f(i-1,j-v)   ,  f(i-1,j-2*v) + w , ..... , f(i-1,j-s*v)+(s-1)*w, f(i-1,j-(s+1)*v)+s*w )

可以求得f(i, j-v)、 f(i-1,j-(s+1)*v)+s*w，

但遗憾的是Max函数并不能通过这两项求出Max(f(i-1,j-v) , f(i-1,j-2*v) + w , ..... , f(i-1,j-s*v)+(s-1)*w)是多少

思路一胎死腹中，(ಥ﹏ಥ)

优化思路二：二进制优化方法

之前每种物品需要遍历 s 次，时间复杂度较高，可以将 s 个物品拆分成 logs 数量级个物品，将这些物品视作新的物品，logs个物品通过只能选择1个或0个进行组合，可以复原成任意 0 ~ s 个物品，举个🌰：

比如某个物品可以使用的数量是 20 个，通过二进制拆分，可以拆成 1、2、4、8、5个这五个新的物品，前四个物品进行选择 0 个或 1 个的组合可以得到 0 ~ 15 个物品，再加上最后一个物品的组合可以得到 5 ~20 个物品。

将每种物品都进行如此拆分，就可以得到 n * logs 个物品，只需要对这些新物品进行 01 背包问题就迎刃而解了。

严格证明

说如何拆分的时候有些 hand waving，接下来我详细说一下究竟如何拆分

设总数量为 s

拆分成 1, 2, 4, 8, ……, 2^k, c 这些数的和为 s

k 的值为 log(s+1) - 1 向下取整，且 c < 2^(k+1)

这样前 k+1 个数用二进制思考很容易想到可以组合成区间 [0, 2^(k+1)-1] 中的任一个整数

加上最后一个数字可以组合成区间 [c , s] 中的任一个整数

又因为 c < 2^(k+1) ，所以两个区间组合在一起可以且仅可以复原成 [0, s] 中的任一个整数

∎

实现细节

v, w, g数组的第0个位置是没有用到的 所以在严格开空间的时候是要注意开 11*n+1, 11*n+1, m+1 个

因为数据量较大，使用二维数组实现的01背包会MLE，要用空间优化过的版本。

参考链接

• O(n)的算法居然超时了，此时的n究竟是多大？

附录

估算运行时间程序

package main

import (
	"fmt"
	"time"
)

func main() {
	for {
		start := time.Now()
		add()
		fmt.Printf("took %v\n", time.Since(start))
	}
}

func add() {
	var i int64
	for ; i < 100000000; i++ {
		i++
	}
}