1. 多重背包算法讲解

多重背包的一个问题就是物品很多的时候如何避免减少运算量。上一题，我们介绍了第一种方法，假设物品在一次循环中没有放入，那么后面也不会放入，就不需要再循环下去了。这一题，我们要介绍一种新的方法，这个方法对于我们后面学一些更难的题目的时候是有铺垫作用的。

我们先用一个具体的数字来举例，假设一种物品，有 7 个。所以，理论上，有多种可能，最终是放入了 i 个这种物品， i 可能的数值为 {0,1,2,3,4,...,7}。我们可以把这 8 种可能看成是 7 个不同的物品，第 i 个物品的重量是 w*i , 价值是 v*i ( 0 可以不考虑， 0 相当于物品 1 不放入 ）。

但是，实际上，可以进一步证明，从 1 到 7 之间的任何一个数，都可以通过从 {1,2,4} 当中选 若干个加起来得到（不重复，可以选，可以不选）：

7 = 4 + 2 + 1
6 = 4 + 2
5 = 4 + 1
4 = 4
3 = 2 + 1
2 = 2
1 = 1

所以，如果一个物品只有 7 件，我们 制造 出 3 个新的物品，重量和价值分别是: {w,v},{2*w,2*v},{4*w,4*v}，然后分别用 01背包 算法来算一下，这个比较好理解。

但是，假设这个物品有 11 个呢？有些同学会说， 11 个物品，那就是分解成 {1,2,4,8} 。这样想是错的，因为，我们把 {1,2,4,8} 都枚举完之后，相当于是满足了有 15 个这种物品的情况，包括 12 件， 13 件， 14 件、 15 件的情况都会考虑上，但是，这个物品只有 11 个，所以，这就超范围枚举了。正确的做法是，把 11 看成了 1+2+4+4 ，任何不超过 11 的整数，都可以分解成 {1,2,4,4} 当中若干个相加：

11 = 7 + 4 = 4 + 2 + 1 + 4
10 = 6 + 4 = 4 + 2 + 4
9 = 5 + 4 = 4 + 1 + 4
8 = 4 + 4 = 4 + 4
7 = 7 + 0 = 4 + 2 + 1
6 = 6 + 0 = 4 + 2
5 = 5 + 0 = 4 + 1
4 = 4 + 0 = 4
3 = 3 + 0 = 2 + 1
2 = 2 + 0 = 2
1 = 1 + 0 = 1

换句话说，不超过 11 的数字 n 分成 2 种情况：

1. n 小于等于 7 ,分解成 {1,2,4} 相加

2. n 大于 7 的: n 先分解成 4 + n', n' 是一个小于等于 7 的数， n' 进一步可以通过 {1,2,4} 分解。

从 11 推广到更广泛的情况。我们对于一个数字 s ( s 是这个物品的个数 )，先转成一个 全码二进制数 和另一个数字相加。这里说的 全码二进制数 是指每一位都是 1 的二进制数。例如，十进制数 1,3,7,15,31,63 都是 全码二进制数。 全码二进制数 的特点是它是 $2^i-1$ 。举例来说：

s=53, 全码二进制数为 31 , 53 = 31 + 21 , 所以可课分解为 {1,2,4,8,16,21}
s=74, 全码二进制数为 63 , 74 = 63 + 11 , 所以可课分解为 {1,2,4,8,16,32,11}
s=99, 全码二进制数为 63 , 99 = 63 + 36 , 所以可课分解为 {1,2,4,8,16,32,36}

假设有 2000 件相同的物品， 2000 可以分解成 {1,2,4,8,16,32,64,128,256,512,977 } ,相当于是有 11 件不同的物品，循环的次数就从循环 2000 次变成了循环 11 次，效率大大提升。

2. 例题

题目描述

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

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

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

输出最大价值。

输入格式

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

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

数据范围

0 < 1000 < N , C ≤2000 , 0 < $v_i$ , $w_i$ , $s_i$ ≤ 1000

输出格式

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

样例

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

8

程序填空

#include<bits/stdc++.h>
using namespace std;
int dp[2001];
int main()
{
	int n,c;
	scanf("%d%d",&n,&c);
	
	int i,j,w,v,s,t,ww,vv,cnt;
	
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&w,&v,&s);
		//全码二进制数对应的物品
		t=1;
		while(t<=s)
		{
			s -= t;
			ww = 填空(1);
			vv = 填空(2);
			for(j=c;j>=填空(3);j--)
				dp[j] = max(填空(4),dp[j]);
			t = t*2;
		}

		//剩余数量构成的物品
		if(填空(5))
		{
			ww = 填空(6);
			vv = 填空(7);
			for(j=c;j>=ww;j--)
				dp[j] = max(填空(8),dp[j]);
		}

	}
	printf("%d",dp[c]);

	return 0;
}

填空(1)：{{ input(1) }}

填空(2)：{{ input(2) }}

填空(3)：{{ input(3) }}

填空(4)：{{ input(4) }}

填空(5)：{{ input(5) }}

填空(6)：{{ input(6) }}

填空(7)：{{ input(7) }}

填空(8)：{{ input(8) }}