#include<iostream> #include<string> using namespace std; int v[1000]; int w[1000]; int dp[1000]; int main() { int n; int m; cin>>n>>m; for(int i=0;i<m;i++){ cin>>v[i]>>w[i]; } for(int i=0;i<m;i++){ for(int j=n;j>=v[i];j--){ dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } cout<<dp[n]<<endl; } |
Double click to view unformatted code.