疯狂的采药（完全背包例题详解）

题目

每种草药可以无限制地采摘，每种草药对应采药时间、草药价值，求在一定的采药时间下，采出的药最大总价值是多少。

输入格式
输入第一行有两个整数，分别代表总共能够用来采药的时间 t 和代表山洞里的草药的数目 m。
第 2 到第(m+1)行，每行两个整数，第(i + 1) 行的整数 ai,bi分别表示采摘第 i 种草药的时间和该草药的价值。

输出格式
输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入输出样例
输入
70 3
71 100
69 1
1 2
输出
140
说明/提示
数据规模与约定
对于 30% 的数据，保证m≤10 ³。
对于 100% 的数据，保证 1≤m≤10 ⁴，1≤t≤10 ⁷，且 m ×t<10 ⁷，1≤ai，bi≤10⁴ 。

方法一：简单完全背包思路

枚举每种背包可能取到的药草情况，维护出每个空间大小的最大价值。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct node{
	int time, value;
}flower[10010];

ll dp[10000010];

int main(){
	int total, sum;
	scanf("%d%d", &total, &sum);
	for(int i=0; i<sum; i++){
		scanf("%d %d", &flower[i].time, &flower[i].value);
	}
	
	for(int i=1; i<=total; i++){
		for(int j=0; j<sum; j++){
			for(int k=0; k*flower[j].time<=i; k++){
				dp[i] = max(dp[i], dp[i-k*flower[j].time]+k*flower[j].value);
			}
		}
	}
	printf("%d", dp[total]);
	
	return 0;
}

思路没错，但由于数据过大，出现超时的情况。

方法二：思路优化

方法一：枚举背包大小（时间），按药草类型再放入不同数量的药草，维护不同背包可装入的最大价值。
方法二：按药草类型放入背包，维护不同背包可装入的最大价值。
方法二较为巧妙。采第 i 个草药的时间大于或等于背包大小 j 那么可以尝试将该草药装入。这样既能就能将全部情况枚举出，又避免了判断草药放入背包的数量。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct node{
	int time, value;
}flower[10010];

ll dp[10000010];

int main(){
	int total, sum;
	memset(dp, 0, sizeof(dp));
	
	scanf("%d%d", &total, &sum);
	for(int i=0; i<sum; i++){
		scanf("%d %d", &flower[i].time, &flower[i].value);
	}
	
	for(int i=0; i<sum; i++){	
	//选一种草药 
		for(int j=flower[i].time; j<=total; j++){
		//尝试可放入草药的背包 
			dp[j] = max(dp[j], dp[j-flower[i].time]+flower[i].value);
		}
	}
	
	printf("%lld", dp[total]);
	
	return 0;
}