0/1 knapsack DP

 

0/1 knapsack

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define endl "\n"

ll val[100005];

ll wt[100005];

ll dp[105][100005];

ll func(ll ind,ll amount)

{

    if(amount==0)return 0;

    if(ind<0)return 0;

    if(dp[ind][amount]!=-1)return dp[ind][amount];

    ll ans;

    ans=func(ind-1,amount);

    if(amount-wt[ind]>=0)

    {

        ans=max(ans,func(ind-1,amount-wt[ind])+val[ind]);

    }

    return dp[ind][amount]=ans;

}

int main()

{

   ios_base::sync_with_stdio(0);

   cin.tie(0);

   cout.tie(0);

  memset(dp,-1,sizeof(dp));

   ll n,w;

   cin>>n>>w;

   for(ll i=0;i<n;i++)

   {

       cin>>wt[i]>>val[i];

 

   }

   cout<<func(n-1,w)<<endl;

 

 

 

 

 

 

    return 0;

 

}