1. 无限背包算法解释

无限背包是只物品的数量是无限的，取之不尽的，只要你觉得划算，又放得下，那你就可以不断的放入。

我们学 多重背包 算法的时候，曾经引入过一个 cnt 变量去计算是否放入多 1 个该物品。如果本轮是不放，那么就不需要再循环下去了。这个算法思想对于无限背包算法同样是有效的，起码，理论上是有效的（后面会讲更好的办法，所以一般不会用这个理论上行得通的办法）。

大家请看下文中的 采灵芝，我们假设到了某一轮循环，该灵芝已经不会在放入（意味着，后面虽然还剩很多该灵芝，但是已经不起作用了），我们如果继续讨论之前 多重背包 的算法思路，应该这样写代码：

	scanf("%d%d",&t,&m);
	while(m--)
	{
		scanf("%d%d",&w,&v); //w就是时间，v就是价值 
		do
		{
			cnt = 0;
			for(j=t;j>=w;j--)
			{
				if(dp[j-w]+v>dp[j])
				{
					cnt++;
					dp[j] = dp[j-w]+v;
				}
			}
		}while(cnt>0); // do {} while 语句是最少循环一次
	}
	printf("%d",dp[t]);

要跳出里面的while(cnt>0)的循环，cnt 必须为 0 ，也就是说，最里面的 if 语句就没有成功过哪怕一次，循环 j 的时候，每一次判断，都是 dp[j-w]+v <= dp[j]。既然，如此，我们可以倒过来，用一层循环去提到里面的 2 层循环，但是，我们需要改变一下循环的方向：

	scanf("%d%d",&t,&m);
	while(m--)
	{
		scanf("%d%d",&w,&v); //w就是时间，v就是价值 

		for(j=w;j<=t;j++)
			dp[j] = max(dp[j-w]+v,dp[j]);
	}
	printf("%d",dp[t]);

上面的两种代码，本质上是一样的，但是效率上差异很大，后者少了一层循环。我们一旦理解之后，只需要记住下面这种，用第 1 种解题会被别人笑话的。

2. 例题

题目： 采灵芝

题目描述

仙岛上种了无数的不同种类的灵芝，小芳跟着爷爷来到仙岛采摘灵芝。由于他们带的食物和饮用水有限，必须在时间 t 内完成采摘。

假设岛上有 m 种不同种类的灵芝，每种灵芝都有无限多个，已知每种灵芝采摘需要的时间，以及这种灵芝的价值；

请你编程帮助小芳计算，在有限的时间 t 内，能够采摘到的灵芝的最大价值是多少？

输入格式

第一行有两个整数 T（1 < T <= 100000）和 M（1 <= M <= 2000 ），用一个空格隔开，T 代表总共能够用来采灵芝的时间，M 代表岛上灵芝的种类数。

接下来的 M 行每行包括两个在 1 到 10000 之间（包括 1 和 10000 ）的整数，分别表示采摘某种灵芝的时间和这种灵芝的价值。

输出格式

一个整数，表示在规定的时间内，可以采到的灵芝的最大总价值。

样例

70 3
71 100
69 1
1 2

140

程序填空

#include<bits/stdc++.h>
using namespace std;
int dp[100001];
int main()
{
	int m,t;
	scanf("%d%d",&t,&m);
	
	int j,w,v;
	
	while(m--)
	{
		scanf("%d%d",&w,&v); //w就是时间，v就是价值 

		for(填空(1);填空(2);填空(3))
			dp[j] = max(填空(4),dp[j]);
	}
	printf("%d",dp[t]);

	return 0;
}

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

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

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

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