#include<iostream> #include<stdio.h> #include<string> #include<string.h> #include<cmath> #include<math.h> #include<vector> #include<algorithm> using namespace std; int main(){ int n,m; cin>>m>>n; int dp[n+1][m+1]; for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ dp[i][j]=0; } } int v[n+1],c[n+1]; for(int i=1;i<=n;i++){ cin>>c[i]>>v[i]; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j<c[i]) dp[i][j]=dp[i-1][j]; else dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+v[i]); } } cout<<dp[n][m]; return 0; } |
Double click to view unformatted code.