0-1 Knapsack Problem

Reading time: 20 minutes | Coding time: 10 minutes

Given n items, in which the ith item has weight wi and value vi, find the maximum total value that can be put in a knapsack of capacity W. You cannot break an item, either pick the complete item, or don't pick it.

This is a companion discussion topic for the original entry at http://iq.opengenus.org/0-1-knapsack-problem/

int max(int a, int b)
return (a > b)? a : b;

int knapSack( int W, int wt[], int val[], int n) `


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

if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);
return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1), knapSack(W, wt, val, n-1) );

1 Like