the value of weights droppable in bag of capacity W)
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.
force solution will involve all the sets. Number of such sets will be
to consider all sets, we need a recursive solution which will
consider max among 2 cases at each step:
1 : with weight M, find max-weights among M-1 weights which can be
put in bag of capacity W-M
2 : without weight M, find max-weights among M-1 weights which can be
put in bag of capacity W
lookup table here will be made between W and numWts.
The above can be modified to use auxiliary space of just a single
array of size W
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).