#include<iostream> #include<string> #include<algorithm> #include<math.h> #include<vector> using namespace std; int main(){ int W,K; cin>>W>>K; int thing[K]; int heat[K]; int dp[W+1]; for(int i=0;i<=W;i++){ dp[i]=0; } for(int i=0;i<K;i++){ cin>>thing[i]>>heat[i]; } for(int i=0;i<K;i++){ for(int j=W;j>=thing[i];j--){ dp[j]=max(dp[j],dp[j-thing[i]]+heat[i]); } } cout<<dp[W]<<endl; } |
Double click to view unformatted code.