0/1 knapsack

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int wt[105], val[105];
int dp[105][100005];

int func(int ind, int wt_left)
{
    if (wt_left == 0)
        return 0;
    if (ind < 0)
        return 0;
    if (dp[ind][wt_left] != -1)
        return dp[ind][wt_left];
    // Don't choose
    int ans = func(ind - 1, wt_left);
    // Choose
    if (wt_left - wt[ind] >= 0)
        ans = max(ans, func(ind - 1, wt_left - wt[ind]) + val[ind]);
    return dp[ind][wt_left] = ans;
}
void printDPArray(int n, int w)
{
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= w; j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    memset(dp, -1, sizeof(dp));
    int n, w; // n=no of item, w= knapsack weight
    cin >> n >> w;
    for (int i = 0; i < n; i++)
    {
        cin >> wt[i] >> val[i];
    }
    cout << func(n - 1, w);
    printDPArray(n, w);

    return 0;
}
/*
3 8
3 30
4 50
5 60
*/

/////////////////////////////////////////////////////////////////////////
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n ,max_weight;
    cin >> n>> max_weight;
    int profit[n+1],weight[n+1];
    for(int i =0 ; i< n ;i++)
    {
        cin >> profit[i];
    }
    for(int i =0 ; i < n ;i++)
    cin >> weight[i];
    
    int v [n+1][max_weight+1];
    for(int i =0 ; i<=n;i++ )
    {
        for(int w=0 ; w<=max_weight ; w++)
        {
            if(w == 0 or i == 0)
            v[i][w] = 0;
            else if( weight[i] <=w ) 
            {
                v[i][w] = max ( profit[i] + v[i-1][w-weight[i]], v[i-1][w]);
            }
            else 
            v[i][w] = v[i-1][w];
        }
    }
    for(int i=0 ; i<=n ; i++)
    {
        for(int w=0;w<=max_weight;w++)
        {
            cout << v[i][w] << " ";
        }
        cout << endl;
    }
}
//////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
#define N 2e6
#define ll long long
using namespace std;
ll wt[105], cost[105], vol[105];
int V;
ll dp[105][105][105];
ll func(ll i, ll weight_left, ll volume)
{
    if (weight_left == 0 && volume >= V)
        return 0;
    if (i < 0 && volume >= V)
        return 0;
    if (weight_left == 0 || i < 0)
        return INT_MIN;
    if (dp[i][weight_left][volume] != -1)
        return dp[i][weight_left][volume];
    ll x = func(i - 1, weight_left, volume);
    if (weight_left - wt[i] >= 0)
        x = max(func(i - 1, weight_left - wt[i], volume + vol[i]) + cost[i], x);
    return dp[i][weight_left][volume] = x;
}
int main()
{
    ll n, weight;
    cin >> n >> weight >> V;
    memset(dp, -1, sizeof(dp));
    for (ll i = 0; i < n; i++)
    {
        cin >> wt[i] >> cost[i] >> vol[i];
    }
    cout << func(n - 1, weight, 0) << endl;
}