01背包模板

二维dp：

#include<iostream>
using namespace std;
const int N = 110;
int dp[N][N];
//dp[i][j]代表前i株草药能装进背包容积为j时能获取的最大价值 
int w[N],v[N];//草药消耗的时间和价值 
int main(){
	int t,m;
	cin>>t>>m;
	//输入题目信息 
	for(int i=1;i<=m;i++){
		cin>>w[i]>>v[i];
	} 
	//i从1-m,dp数组的行下标是从第i株到第m株去选择 
	//j从t-0,dp数组的列下标是从最初始背包容积（剩余时间）去消耗 
	for(int i=1;i<=m;i++){
		for(int j=t;j>=0;j--){
			//是不是就可以判断要不要采 
			//如果剩余时间大于第i株所要采的草药时间，就neng他！
			if(j>=w[i]) {
				//不是一定要采的，而是要看消耗时间去采了之后，能不能得到更大值 
				dp[i][j] = max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]); 
			}else{
				//不能采的话，那就不更新，即为采前i-1株采药时获取的最大价值 
				dp[i][j] = dp[i-1][j];
			} 
		} 
	}
	//最后输出m株草药在t的时间内所获取的最大价值 
	cout<<dp[m][t]<<endl; 
	
	
	return 0;
}

一维：

#include<iostream>
using namespace std;
const int N = 1e7+10;
int dp[N];
int w[N],v[N];//草药消耗的时间和价值 
int main(){
	int t,m;
	cin>>t>>m;
	//输入题目信息 
	for(int i=1;i<=m;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=t;j>=w[i];j--){
			dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
		}
	} 
	
	cout<<dp[t];
	
	
	
	return 0;
}