简简单单的01背包

本蒟蒻第n次写题解
一维dp：

//烙铁题解
#include<bits/stdc++.h>
using namespace std;
//一维dp
int dp[1001];//背包
int c[101],v[101];//c代表采药的时间，v表示草药的数目
int T,M;//T是时间总数，M是草药个数
int main(){
	cin>>T>>M;//输入
	for(int i = 1;i<=M;i++){
        cin>>c[i]>>v[i];
	}
	for(int i = 1;i<=M;i++){//遍历每个草药
        for(int j = T;j>=c[i];j--){//遍历c[i]~T，切记要倒序
            dp[j]=max(dp[j],dp[j-c[i]]+v[i]);//迭代
        }
	}
	cout<<dp[T];//简单输出，撒花~
	return 0;
}
//最后写上去，提交，等待一下，AC~~~

二维的：

//烙铁题解
#include<bits/stdc++.h>
using namespace std;
//二维dp
int dp[1001][1001];//背包（二维）
int c[101],v[101];//c代表采药的时间，v表示草药的数目
int T,M;//T是时间总数，M是草药个数
int main(){
	cin>>T>>M;//输入
	for(int i = 1;i<=M;i++){
        cin>>c[i]>>v[i];
	}
	for(int i = 1;i<=M;i++){//遍历每个草药
        for(int j = 1;j<=T;j++){//遍历1~T
            if(j>=c[i]){//判断一下是否>=c[i]，如果j<c[i]的话dp[j-c[i]]会越界
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+v[i]);//迭代
            }else{
                dp[i][j]=dp[i-1][j];//把上一次的结果复制下来
            }
        }
	}
	cout<<dp[M][T];//简单输出，撒花~
	return 0;
}
//最后写上去，提交，等待一下，AC~~~

其实题目很简单，像我一样的蒟蒻都能做