Saleh127

SPOJ PIGBANK / DP - Knapsack

Dec 2nd, 2021
1,043
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-12-03-00.57.20
  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.  
  12. ll dp[20005];
  13. ll p[505],w[505];
  14.  
  15.  
  16. int main()
  17. {
  18.    ios_base::sync_with_stdio(0);
  19.    cin.tie(0);cout.tie(0);
  20.  
  21.    test
  22.  
  23.    {
  24.         ll n,m,i,j,k,l,e,f;
  25.  
  26.         cin>>e>>f>>n;
  27.         f-=e;
  28.  
  29.         for(i=1;i<=20000;i++) dp[i]=1e12;
  30.  
  31.         dp[0]=0;
  32.  
  33.         for(i=0;i<n;i++)
  34.         {
  35.              cin>>p[i]>>w[i];
  36.         }
  37.  
  38.         for(i=0;i<n;i++)
  39.         {
  40.              for(j=w[i];j<=f;j++)
  41.              {
  42.                   dp[j]=min(dp[j],dp[j-w[i]]+p[i]);
  43.              }
  44.         }
  45.  
  46.         if(dp[f]==1e12) cout<<"This is impossible."<<nl;
  47.         else cout<<"The minimum amount of money in the piggy-bank is "<<dp[f]<<"."<<nl;
  48.    }
  49.  
  50.  
  51.  
  52.    get_lost_idiot;
  53. }
  54.  
RAW Paste Data