背包問題
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?in("inflate.in");
ofstream?out("inflate.out");
int?points[10000];
int?minutes[10000];
int?dp[10001];
int?n;
int?m;
void?solve()
{
????int?res?=?0;
????in>>m>>n;
????for(int?i=0;i<n;++i)
????????in>>points[i],in>>minutes[i];
????memset(dp,0,sizeof(dp));
????for(int?i=0;i<n;++i){
????????for(int?j=minutes[i];j<=m;++j){
????????????dp[j]?=?max(dp[j-minutes[i]]+points[i],dp[j]);
????????}
????}
????out<<dp[m]<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}