0-1 Knapsack problem.c

#include <cstdlib>
#include <algorithm>
#include <climits>
#include <cstdio>
using namespace std;
#define DUMMY 5454
int A[1000000];
int val[] = {DUMMY, 60, 100, 120};
int wt[] = {DUMMY, 10, 20, 30};
int knapSack(int N, int W){
    for(int i = 0; i<= W; i++) A[i] = 0;

    for(int i = 1; i<= N; i++)
        for(int j = W; j>0; j--){
            if(wt[i]<= j) A[j] = max(A[j], val[i] + A[j - wt[i]]);
        }
   return A[W];
}
int main()
{

    int  W = 50;
    int n = sizeof(wt)/sizeof(wt[0]);
    printf("%d", knapSack(n-1, W));
    return 0;
}

/*
#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)
                 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];
       }
   }

   return K[n][W];
}

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