SPOJ – KNAPSACK – The Knapsack Problem

1. #include<stdio.h>

   #include<iostream>
   #include<string>
   #define sci(x) scanf(“%d”,&x)
   #define scll(x) scanf(“%lld”,&x)
   #define pfi(x) printf(“%d”,x)
   #define pfll(x) printf(“%lld”,x)
   #define ch(x) scanf(“%c”,&x)
   using namespace std;
   typedef long long ll;
   /*float stof(const string& str, size_t *idx = 0);
   double stod(const string& str, size_t *idx = 0);
   long double stold(const string& str, size_t *idx = 0);
   int stoi(const string& str, size_t *idx = 0, int base = 10);
   long stol(const string& str, size_t *idx = 0, int base = 10);
   unsigned long stoul(const string& str, size_t *idx = 0, int base = 10);
   long long stoll(const string& str, size_t *idx = 0, int base = 10);
   unsigned long long stoull(const string& str, size_t *idx = 0, int base = 10); */
   ll max(ll a,ll b)
   {
   if(a>b)
   return a;
   else
   return b;
   }
   ll n;
   ll dp[2002][2002];
   ll s[2003];
   ll v[2003];
   ll ks(ll idx,ll rs)
   {
   if(idx==n || rs==0)
   return 0;
   if(dp[idx][rs]!=-1)
   return dp[idx][rs];
   if(s[idx]<=rs)
   return dp[idx][rs]=max(v[idx]+ks(idx+1,rs-s[idx]),ks(idx+1,rs));
   if(s[idx]>rs)
   return dp[idx][rs]=ks(idx+1,rs);
   }
   int main()
   {
   ll si;
   scll(si);
   scll(n);
   ll i,j;
   for(i=0;i<=2000;i++)
   {
   for(j=0;j<=2000;j++)
   dp[i][j]=-1;
   }
   for(i=0;i<n;i++)
   {
   scll(s[i]);scll(v[i]);
   }
   ll k=ks(0,si);
   pfll(k);
   return 0;

   }