0/1-Kanpsack Algorithm

Suppose you have been ordered to bring some elements from a place where there are  boxes full of precious elements.

( each box contains elements of only one type. ) . Each element has a weight  and a value  , where  denotes the box number.

You are told  all the parameters ( weight and value ) of the boxes in advance . But you can not carry more than  units of weight  with your knapsack .Because your boss has given this to you. Now the problem is to find out   what is the highest amount of profit you can make with the knapsack you have. ( The more you make profit, the more your boss become impressed.)

Now take the pencil  and paper and figure out what you should do . Consider one box at a time. Say the box number is  .(Assume that there is no box whose number is higher than  ) You can make two things with the  box,  

Case 1: Pick an element from the box . It will cause your knapsack size to be reduced by  , adding  to your total amount of profit.

Case 2: Do not pick an element from the box. That will cause the number of boxes you are considering , reduced by one that is . ( Be careful , when you are not taking an element from on box , you are discarding the box from your consideration. In future you will not be able to take any element from that box )

let  denote the profit you can make when you have  sized knapsack and  boxes. Then according to the first one of the cases above , you have 

                      , 

that is your knapsack size is shorten by  and you have added  to the total amount of profit possible by the reduced knapsack.

Other case says the following ,

                               

that is , you are assuming that you have only  boxes .

The problem is a maximization problem. So you have to take the maximum of the two situation . Then the solution becomes ,

and your destination is to find . Here Knapsack size means how much of weight it can hold.