题目链接
思路:
基础01背包DP。
代码:
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=6e6+10;
const int M=2e4+5;
const double eps=1e-8;
const int mod=998244353;
const int inf=0x7fffffff;
const double pi=3.1415926;
using namespace std;
int w[105],val[105];
int dp[105][1005];
signed main()
{IOS;int t,m,res=-1;cin>>t>>m;for(int i=1;i<=m;i++){cin>>w[i]>>val[i];}for(int i=1;i<=m;i++){for(int j=t;j>=0;j--){if(j>=w[i]){dp[i][j]=max(dp[i-1][j-w[i]]+val[i],dp[i-1][j]);}else{dp[i][j]=dp[i-1][j];}}}cout<<dp[m][t]<<endl;return 0;
}