Knapsack Problem
(Maximize
the value of weights droppable in bag of capacity W)
Given
2 integer arrays: wt[] and val[] (each of length numWts). Each weight
has a value associated with it (say the price of the weight). Our
objective is to find value of maximum price obtainable by selling a
bagful of weights. Capacity of the bag is W.
Brute
force solution will involve all the sets. Number of such sets will be
2^{numWts}
So,
to consider all sets, we need a recursive solution which will
consider max among 2 cases at each step:
case
1 : with weight M, find maxweights among M1 weights which can be
put in bag of capacity WM
case
2 : without weight M, find maxweights among M1 weights which can be
put in bag of capacity W
The
lookup table here will be made between W and numWts.
Note:
The above can be modified to use auxiliary space of just a single
array of size W
Element
at index i in this array will store maximum value obtainable for
weight i from k weights. Then we can see the effect of introducing
weight k+1 on this array (as done for previous problems).
