Advertisement
Saleh127

SPOJ KNAPSACK / DP

Nov 6th, 2021
640
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-06-17.41.50
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11. ll dp[5000][5000];
  12.  
  13. int main()
  14. {
  15.     ios_base::sync_with_stdio(0);
  16.     cin.tie(0);
  17.     cout.tie(0);
  18.  
  19.  
  20.     ll s,n,i,j,k,l;
  21.  
  22.     cin>>s>>n;
  23.  
  24.     ll a[n+4],b[n+4];
  25.  
  26.     for(i=1; i<=n; i++) cin>>a[i]>>b[i];
  27.  
  28.  
  29.     for(i=1;i<=n;i++)
  30.     {
  31.          for(j=1;j<=s;j++)
  32.          {
  33.               if(a[i]<=j)
  34.               {
  35.                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+b[i]);
  36.               }
  37.               else
  38.               {
  39.                    dp[i][j]=max(dp[i-1][j],dp[i][j]);
  40.               }
  41.          }
  42.     }
  43.  
  44.  
  45.     cout<<dp[n][s]<<nl;
  46.  
  47.     get_lost_idiot;
  48. }
  49.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement