思路

01 背包模版题，用了记忆化搜索，详见注释。

code

#include<bits/stdc++.h>
using namespace std;
const int MAX=1005;
int T,M;
int v[MAX],w[MAX];
int DP[MAX][MAX];
int dp(int x,int SPV){
	if(x>M){//如果类型超过总数
		return 0;
	}else{
		if(DP[x][SPV]!=0)   return DP[x][SPV];//如果搜过了
		if(v[x]>SPV){//如果选这个超过了时间
			DP[x][SPV]=dp(x+1,SPV);//选下一个
		}else{
			DP[x][SPV]=max(dp(x+1,SPV),dp(x+1,SPV-v[x])+w[x]);//在选或不选中选最优一个
		}
	}
	return DP[x][SPV];
}
int main(){
	cin>>T>>M;
	for(int i=0;i<M;i++){
		cin>>v[i]>>w[i];
	}
	int result=dp(0,T);
	cout<<result;
	return 0;
}