[AtCoder] E - Knapsack 2

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E - Knapsack 2
Source            : AtCoder Educational DP Contest
Category          : Dynamic Programing
Algorithm         : Exchange Arguments Technique
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll          long long int   
#define inf         (ll)1e17  
  
static const int maxn = 100 + 5;  
static const int Max = 1e5 + 5;  
  
ll dp[maxn][Max];  
bool memoize[maxn][Max];  
  
int w[maxn], val[maxn];  
  
int N, W;  
  
ll solve(int pos, int make)  
{  
  if (pos >= N)   
  {  
      if (make == 0) return 0;  
      return inf;  
  }  
  ll &ret = dp[pos][make];  
  bool &mem = memoize[pos][make];  
  if (mem) return ret;  
  mem = 1;  
  ret = inf;  
  if (make - val[pos] >= 0) ret = min(ret, w[pos] + solve(pos+1, make - val[pos]));  
  ret = min(ret, solve(pos+1, make));  
  return ret;  
}  
                                        
int main()  
{  
    scanf("%d %d", &N, &W);  
    for (int i = 0; i < N; i++) scanf("%d %d", &w[i], &val[i]);  
    for (int make = 100000; make >= 0; make--)  
    {  
        ll ans = solve(0, make);  
        if (ans <= W)   
        {  
            printf("%d\n", make);  
            break;  
        }  
    }  
}