Make delicious recipes!

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 2numWts


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 max-weights among M-1 weights which can be put in bag of capacity W-M

case 2 : without weight M, find max-weights among M-1 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).




Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal