0/1 knapsack

#include <bits/stdc++.h>
using namespace std;
vector<int>w,v;
int n, W;
vector<vector<int>>dp;
int kSack(int W , int i) {

    if (i < 0)
        return 0;

    if (dp[i][W] != -1)
        return dp[i][W];

    if (w[i] > W) {
        dp[i][W] = kSack(W, i - 1);
    }
    else {
        dp[i][W] = max( ( v[i] + kSack(W - w[i], i - 1)  )  , kSack(W,i - 1)  );
    }

    return dp[i][W];
}

int main() {
    cin >> n >> W;
    dp.assign(n, vector<int>(W + 1, -1));
    for (int i = 0; i < n; i++) cin >> w[i];
    for (int i = 0; i < n; i++) cin >> v[i];
    cout << kSack(W , n-1) << endl;
    return 0;
}