题解 | #采药#类背包问题

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n,m;
	int t[100],v[100];
	while(cin>>n>>m)
	{
		int dp[m+1][n+1];
		for(int i=1;i<=m;i++)
		{
			cin>>t[i]>>v[i];
		}
		for(int i=0;i<=m;i++)
		for(int j=0;j<=n;j++)
		{
			if(i==0) 		dp[i][j]=0;
			else if(t[i]<=j) dp[i][j]=max(dp[i-1][j-t[i]]+v[i],dp[i-1][j]);
			else			dp[i][j]=dp[i-1][j];
		}
		cout<<dp[m][n]<<endl;
	}
	return 0;
}