0-1 Knapsack DP

#include <iostream>
#include <algorithm>
#include <vector>

int cache[100][100] = {0};

int knapsack_DP(int W, int wt[], int val[], int n){

    int K[W+1][n+1] = {0};
    for(int i=0; i<=W; i++){
        for(int j=0; j<=n; j++){
            if(i==0 || j == 0)
                K[i][j] = 0;
            else{
                if(wt[j-1] > i)
                    K[i][j] = K[i][j-1];
                else{
                    int taken = val[j-1] + K[i-wt[j-1]][j-1];
                    int not_taken = K[i][j-1];
                    K[i][j] = std::max(taken,not_taken);
                }
            }
        }
    }
    return K[W][n];
}

int knapsack_cache(int W, int wt[], int val[], int n){

    if(n==0 || W == 0)
        return 0;

    if(wt[n-1] > W){
        if(cache[W][n-1] == -1)
            cache[W][n-1] = knapsack_cache(W,wt,val,n-1);
        return cache[W][n-1];
    }

    if(cache[W-wt[n-1]][n-1]==-1){
        cache[W-wt[n-1]][n-1] = knapsack_cache(W-wt[n-1], wt, val, n-1);

    }
    int taken = val[n-1] + cache[W-wt[n-1]][n-1];
    if(cache[W][n-1] == -1){
        cache[W][n-1] = knapsack_cache(W, wt, val, n-1);
    }
    int not_taken = cache[W][n-1];
    return std::max(taken, not_taken);
}

int knapsack_recur(int W, int wt[], int val[], int n){

    if(n==0 || W == 0)
        return 0;

    if(wt[n-1] > W)
        return knapsack_recur(W,wt,val,n-1);

    int taken = val[n-1] + knapsack_recur(W-wt[n-1], wt, val, n-1);
    int not_taken = knapsack_recur(W, wt, val, n-1);

    return std::max(taken, not_taken);
}


int main(){
    int value[] = {60,100,120};
    int weight [] = {10,20,30};
    int W = 50;

    int n = sizeof(value)/sizeof(value[0]);
    std::cout << knapsack_recur(W,weight,value,n) << std::endl;

    for(int i=0; i<W; i++){
        for(int j=0; j<n; j++){
            cache[i][j] = -1;
        }
    }

    std::cout << knapsack_cache(W,weight,value,n)<<std::endl;

    std::cout << knapsack_DP(W,weight,value,n);

    return 0;
}