GeeksforGeeks : Knapsack

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back

ll n,wm,ans;
ll w[1010];
ll v[1010];

ll m[1010][1010];

void nill(){
    for(int i=0;i<1010;i++)
        for(int j=0;j<1010;j++)
            m[i][j] = -1;
}

ll solve(ll k,ll i){
    if(i==n || k==0)
        return 0;
    if(m[k][i] != -1)
        return m[k][i];

    if(w[i] > k)
        return m[k][i] = solve(k,i+1);

    return m[k][i] = max(v[i] + solve(k-w[i],i+1), solve(k,i+1) );

}

int main(){
ios::sync_with_stdio(false);

    int t; cin >> t;
    while(t--){
        nill();
        cin >> n >> wm;

        for(int i=0;i<n;i++)
            cin >> v[i];
        for(int i=0;i<n;i++)
            cin >> w[i];

        cout << solve(wm,0) << endl;
    }

    return 0;
}