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

「爱情、让人受尽委屈。」 2022-11-27 05:23 122阅读 0赞

### 题目 ###

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

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

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

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

--------------------

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

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

#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;
    }