1. 多重背包算法讲解

所谓多重背包，就是说同一种物品有若干个，这里说的若干是有上限的，例如就是 5 个，或者是 7 个，是一个明确的、有限的数字。对于这种物品，可以不放入背包，可以放入 1 个，或者 2 个....，但是不能超过这个物品的个数（上限）。

对于这种情况，处理方法很简单，还是基于 01背包 算法的思想，我把这几个相同的物品看成是不相同的物品去处理就行了，每个都套用 01背包 的算法去算一遍，只要不超时就行，准确性是可以保证的。

保证了准确性之后，还要保证效率。有一些题目，同一种物品的数量很大，好几千，物品的种类又好几千，背包的容积又很大，好几千。几个好几千相乘，那就不得了，就会超时了。解决的办法之一，就是如果一个一个物品在本轮已经不在装进去了，那么就不需要再循环下去了，再循环下去也是不会装进去的。所以，需要增加一个计数器看这个物品是否装进去了，最终如果计数器为 0 ，就可以跳出循环。

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,cnt=0;
	
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&w,&v,&s);
		while( 填空(1) )
		{
			填空(2) ;
			for(j=c;j>=w;j--)
			{
				if(填空(3))
				{
					cnt++;
					dp[j] = dp[j-w]+v;
				}
			}
			if(填空(4))  //提高效率用的，如果 s 很小就不需要
				break;
		}
	}
	printf("%d",dp[c]);

	return 0;
}

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

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

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

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