完全揹包#洛谷 P1616 瘋狂的採藥

題目描述
LiYuxiang 是個天資聰穎的孩子，他的夢想是成爲世界上最偉大的醫師。爲此，他想拜附近最有威望的醫師爲師。醫師爲了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞裏對他說：「孩子，這個山洞裏有一些不同種類的草藥，採每一種都需要一些時間，每一種也有它自身的價值。我會給你一段時間，在這段時間裏，你可以採到一些草藥。如果你是一個聰明的孩子，你應該可以讓採到的草藥的總價值最大。」

如果你是 LiYuxiang，你能完成這個任務嗎？

此題和原題的不同點：

11. 每種草藥可以無限制地瘋狂採摘。

12. 藥的種類眼花繚亂，採藥時間好長好長啊！師傅等得菊花都謝了！

思路：
這是一道完全揹包問題。
完全揹包的模板題面是這樣的：設有n種物品，每種物品有一個重量及一個價值。但每種物品的數量是無限的，同時有一個揹包，最大載重量爲M，今從n種物品中選取若幹件(同一種物品可以無限選取)，使其重量的和小於等於M，而價值的和爲最大。
本題與上面的描述中共同擁有的一個特點，每種物品無限個。那麼我們只需要將01揹包的程式碼進行略微修改即可。（01轉多重也只是略微修改）
完全揹包程式碼段：

for(int i=1;i<=n;i++)
 		for(int j=w[i];j<=V;j++)
        	f[j]=max(f[j],f[j-w[i]]+c[i]);

而這是01揹包的核心程式碼段：

for(int i=1;i<=n;i++){
    for(int j=m;j>=s[i];j--){
    	f[j]=max(f[j],f[j-s[i]]+v[i]);}}

AC程式碼：

#include<cstdio>
#include<iostream>
using namespace std;

int a[10005];
int Time[10005];
int ans[10000005];

int main(){
	int t,m;
	scanf("%d%d",&t,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&Time[i],&a[i]);
	}
	
	for(int i=1;i<=m;i++){
		for(int j=Time[i];j<=t;j++){
			ans[j]=max(ans[j],ans[j-Time[i]]+a[i]);
		}
	}
	printf("%d\n",ans[t]);
}