0/1 knapsack problem (dynamic programming)

0/1 knapsack problem (dynamic programming)

This is the top down approach to solve the above mentioned problem using Memoization technique to avoid re computation of overlapping sub problems.

#include<stdio.h>
#define MAXN 20
#define MAXW 100

int look[MAXN][MAXW];
int max(int a, int b) { return (a > b)? a : b; }


int knapSack(int W, int wt[], int val[], int n){
    if(look[n][W]!=-1)return look[n][W];
    if (n == -1 || W == 0)
     return 0;
    
    if (wt[n] > W){
         look[n-1][W]=knapSack(W, wt, val, n-1);
         look[n][W]=look[n-1][W];
    }
    
    else   
       look[n][W]=max( val[n] + knapSack(W-wt[n], wt, val, n-1),knapSack(W, wt, val, n-1));
    
    return look[n][W];
}

int main()
{
 int val[] = {7,4,5,1};
 int wt[] = {5,4,3,1};
 int i,j,W = 7;
 int n = sizeof(val)/sizeof(val[0]);
    for(i=0;i<n;i++)
      for(j=0;j<=W;j++)look[i][j]=-1; 
           printf("%d", knapSack(W, wt, val, n-1));
return 0;
}

Output: 9