01_KnapSack Problem Dynamic Programming

// A Dynamic Programming based solution for 0-1 Knapsack problem
//0_1 knapsack because either we have to take value i.e 1 or discard 0 we can not take fraction.
#include<stdio.h>

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[n+1][W+1];

   // Build table K[][] in bottom up manner
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)

              /*if weight of ith item is less than the weight of  bag then we have two choice

  1.TO go for optimal solution by comapring and find better option

                                   OR

                          2.Simply keep the weight of ith element*/

    K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
printf("KnapSack Matrix");
for(int i=0;i<n+1;i++)
    {
    for(int j=0;j<W+1;j++)
    {
    printf("%d  ",K[i][j]);
    }
    printf("\n");
    }
 //Maximum value will be at the end of matrix
   return K[n][W];
}

int main()
{
    int val[] = {60, 100, 120,150,200,50};
    int wt[] = {10, 20, 30,40,50,60};
    int  W = 100;
    int n = sizeof(val)/sizeof(val[0]);
    printf("Maximum Values=%d", knapSack(W, wt, val, n));
    return 0;
}