0/1 Knapsack Problem Dynamic Programming

Aug 15, 2023

0/1 Knapsack Problem Dynamic Programming

Given a bag which can only take certain weight W. Given list of items with their weights and price. How do you fill this bag to maximize value of items in the bag.
https://www.facebook.com/tusharroy25
https://github.com/mission-peace/inte…
https://github.com/mission-peace/inte…

Content

2 -> Hello friends my name is Tushar and today I'm going to talk about 0/1 knapsack

5.098 -> problem

6.048 -> So I have an old video on this question but I felt I missed

11.032 -> few things in that video so I am creating a new video to fill those

13.045 -> gaps. So what is 0/1 knapsack problem ? Suppose I have a total weight

18.008 -> and then I have certain items with their weights and values.

21.699 -> How do you pick items from this set such that the sum of their values

26.15 -> is maximum but sum of their weights is less than or equal to the total weight.

30.869 -> Also we have just one quantity of each item.

34.059 -> So what does 0/1 means? 0/1 means that either you

37.87 -> pick the item or you don't pick the item. It means that you cannot

41.005 -> split the item.So if it was not a 0/1 knapsack problem

45.329 -> just say that you could have split the item.There's a greedy solution

48.85 -> to solve the question.All you have to do is sort the item

52.629 -> by their value to weight,sort the items by their value

59.079 -> to weight in a non increasing order and then keep picking the items

63.989 -> and then if the last item cannot be picked totally split it up

68.31 -> and pick whatever ratio you can. So but here

71.979 -> we are you doing 0/1 problem,it means that we cannot

75.56 -> split the item. So how do we do it? Yes we will use dynamic programming to solve this

80.047 -> question

81.002 -> In the next section let's see how? So how do we solve this problem

84.799 -> So the question is very simple whenever a new item comes in you have to decide to pick 24 00:01:28,960 --> 00:01:28,192 this item or not

89.092 -> and you have to find which gives you the maximum value. If you pick the item

93.084 -> the maximum value will be the value of the item plus

97 -> whatever we can get by subtracting ,subtracting

100.052 -> this value from the total weight

103.061 -> and excluding this item or the best you can do without including this

107.075 -> item or together

108.899 -> Let's try to understand on with this example.So here i have a

113.329 -> two dimensional matrix and this is a

116.469 -> my total number of columns is same as total weight plus one

119.57 -> and my number of rows is same as the total items.

123.084 -> So our first column is

126.939 -> 0, It means that if the total weight is zero no matter what items I

131.3 -> have my maximum value I can get is always zero. So this is why this all are

135.055 -> zero.

136.013 -> So let's start from here,so if my total weight was 1 and

139.091 -> if I just had one item 1, the best I can do is 1.

144.067 -> So this is the weight of item, the total weight is one.

148.001 -> so the maximum value I can get is just 1.

151.009 -> If my total weight is two, if I just had one item

155.021 -> of weight 1 and whose value is 1 the best I can do is 1.

158.074 -> Remember we just have one quantity of each item.

161.098 -> So even though the total weight is 2 if I just have item 1

165.007 -> again the best I can do is value 1.Similarly

169.074 -> one one one one one. So if the total weight is 7

173.034 -> the only item I have is weight 1 and whose value is 1 the best I can

177.073 -> do is one because we have one quantity of each item.

180.002 -> So next let's introduce 3. Since the total weight is 1

185.003 -> and if the weight of the item is 3 which is greater than one

188.026 -> so three can never be the, can never be selected.

192.041 -> So what we do is what is the best we can do without selecting 3

196.005 -> so basically this number becomes one. Again 2

199.082 -> Since 2 is less than 3, 3 can never be selected.Since this total weight is less than

205.062 -> 3 so the best we can do is

207.056 -> without 3 what is the best we can do which is this number, so that's 1.

210.989 -> Now 3,so

214.1 -> since 3 is,since 3 is less equal to 3,

217.085 -> we have 2 choices, do we select 3 or do we not select 3

222.209 -> If we select this item the

225.36 -> so we have to check what is the best we can do by selecting this item.

229.022 -> If we didn't select this item this gives me a value 4

232.067 -> plus whatever

235.739 -> weight is remaining after we select this weight. So 3

239.23 -> -3 so that's 0. So

243.209 -> t[0] and then

246.52 -> and then we go to the top column so that's also 0.

251.018 -> So we reach this point,so we up,we go 3 steps, we reach this point,3 steps

256.033 -> because the weight of this item is 3

257.098 -> So T[0][0] is 0 or

261.039 -> what is the best value we can do without

263.054 -> selecting this item altogether and that's 1. So this value is 4 and this

268.013 -> value is 1 so max of this is 4.

270.022 -> Alright,

274.001 -> so the total weight is 4 and the item weight is 3.

279.036 -> So again the best I can do is without selecting 3 the best I'm getting is 1.

284.092 -> If I do select 3 the best I can get is

288.029 -> max of by selecting 3 I get a value of 4

293.021 -> plus I subtract

296.03 -> 3 from 4 so that's,that's 1.

299.074 -> and then I go one row up

303.089 -> which is 0 and 1.

307.018 -> So this value 0 and 1

310.022 -> is 1, so 4 plus 1, 5

313.036 -> so max of 4 plus 1,5

316.059 -> or this value 1, so that's 5.

319.068 -> Again where did this 1 came from?

323.007 -> Since we selected this item so

326.074 -> this item gives us a value 4 .So whatever, what is the weight we are left with

331.071 -> your left

332.015 -> the weight we are left with is 1 because this guy is gonna take 3 weight and our total

336.093 -> weight is 4. So we are left with weight of 1

339.009 -> and then we check what is the best we can do if we had

343.073 -> just weight 1 and we did not include item 3, so that's this guy here

348.064 -> which is why we came to this point and the best we can do

351.071 -> if we had a weight 1, total weight 1 and just had a 1 is 1

355.049 -> so that's how we get 4 plus 1,5 and the best we can do without including 3 is 1.

361.011 -> So we get the max of that,so that's 5.Alright,so 5 here,so again

366.001 -> we are checking max of

369.027 -> either 1 or

372.072 -> weight of value of this guy so that's 4 plus

376.076 -> we go up and 3 steps back. 1,1,2,3 and reach this point.

381.095 -> so this guy,so that's 5. So this value will be 5,so it will be 5

386.063 -> all the way till the end.So

389.629 -> if I had a weight,total weight 7 and

391.46 -> if I had 2 items 1 and 3 the best I can do is

396.011 -> max value I can get is 5 which is pretty much selecting both the items.

400.669 -> Let's include 4

404.06 -> so since 4

407.021 -> is greater than 1, this item cannot be picked

410.469 -> if the total weight is 1. So we'll just get the value

414.199 -> without including 4. Without including 4, the best we can do is 1.

417.81 -> Similarly 1,4. So here

422.002 -> at this point if we pick 4

426.077 -> we'll get the max of,if

430.018 -> we pick 4 then the best we can do is 5

434.08 -> plus we go up

438.419 -> and 4 steps back and that's 0 or

442.27 -> the best we can do without picking 4 ,which is 5.So in both the cases we get a value

447.439 -> 5.

448.25 -> So that's go here.

452.025 -> So here the best I can do is

456.699 -> if I pick 4 if I pick item this item

459.96 -> the value this item will give me is 5 plus

465.539 -> subtracting,subtracting 4 from 5 so we are

470.779 -> left with 1 weight and we are left with 2 items so

473.96 -> if we have 1 weight and 2 items that's this value is that value so that's 1

477.081 -> and then if we did not include 4 altogether

481.199 -> the best I can do is 5 so here the max

484.27 -> is 6 so I need to get this 6

487.05 -> We get the value we pick this item

490.071 -> so the value of this item is 5 then we go up

494.289 -> and we go 4 steps back. 4 steps back because 4 is the

497.96 -> weight of this item.1 2 3 4

501.018 -> and we reach this point so we add that value to this

504.909 -> this value so that value is 6 so if we,if we include 4 the best we can do is

509.469 -> 6 and if we don't include 4 the best we can do is 5

512.349 -> So we take 6 here.

515.44 -> So again for 6 the best we can do is by including this item

520.037 -> will be 5 plus going 4 steps back so that's 1

523.729 -> 6 or this guy,so that's 6. So finally lets look up for 7

529.529 -> So here if I pick this item with weight 4 the value I'm getting is

535.35 -> max of 4,5 plus going four steps back

539.061 -> 1 2 3 4 so that's 4.

542.068 -> 1 2 3 4 so that's 4.

546.096 -> or not picking 4 altogether and the best I can do with that is 5.

552.045 -> So clearly 9 is bigger than 5, so this becomes

556.045 -> 9. Alright so if we had total weight 7

561.001 -> and if we had 3 items 1 3 4 the best I can do is

565.012 -> 9. So finally let's bring this last row into the picture.

569.024 -> So since 5 is greater than 1

572.031 -> we cannot include 5 into the action so we just get the value from the top so best we can do

576.279 -> without including 5, so that's 1.

578.14 -> So 1,4,5,so here

582.06 -> so the best if I include 5

586.033 -> if I could decide the best I can do is

589.339 -> max of whatever is the value of 5, so that's 7.

593.61 -> plus whatever is left after removing this

598.052 -> 5 from the total weight,so we are left with 0.So there

602.087 -> and then with the 3 items,with other 3 items so we are left with 0 weight

606.081 -> and we are left with 3 items so that's this guy,so 0 or whatever the best we

611.091 -> could have done without picking 5 altogether so that's 6.

614.097 -> So here the max is 7. So then

619.041 -> we come to this point.So

622.073 -> again what's the best we can do if our total weight is 6

626.062 -> If we pick this item with weight 5 I get the value of

630.086 -> 7 plus we go 5 steps back

634.09 -> 1 2 3 4 5,so 1

638.929 -> and if we don't pick this item altogether the best I got is 6.

642.079 -> So 8. 8 is better than 6.Finally

646.97 -> let's come to this point so if I pick this item

650.619 -> with weight 5 the value I'm getting is 7

655.209 -> plus I subtract 5 from 7 so I'm left with 2 and I'm left with 3 items

661.699 -> so basically we are going 5 steps back here 1,2,3,4,5

665.97 -> So 1 so 7 plus 1,8

669.029 -> or the best we can do without including 5 so that's 9

672.749 -> So here 9 is the winner,so this value is

676.749 -> 9.So this is a value we can,maximum value we can get

682.479 -> by picking items from this set such that the total weight is less than or equal to

687.289 -> 7.So if someone asks you what is the actual,what are the actual items which

691.819 -> we are going to pick?

692.739 -> So let's see how we're going to do that. So we start from this point here

697.549 -> our big,our answer and we'll move and

701.189 -> we'll retrace back in this,in this matrix and try to

705.6 -> find out the actual items.So this 9 we're checking where is this 9 coming from.

710.329 -> This 9

710.999 -> is clearly coming from the top,it's not coming from

715.249 -> this item, it's not coming from this item ,it's coming from the top

718.609 -> It means that since this value is coming from the top it means that

723.229 -> this item is not selected.If this item was selected this value would not be

728.109 -> coming from the top.

729.029 -> So we know that item with weight 5 is not in the answer.

733.239 -> Then we check where's this 9 coming from.

736.459 -> So this nine is clearly not coming from the 5.

740.899 -> So this item must be in the answer so item

746.92 -> 4 with value 5

749.004 -> must be the answer.Then,so this item is selected then we say where do we go from

756.012 -> here.So then we go up and

758.279 -> 4 steps back 1,2,3,4 so this point.

761.72 -> So from here we directly go to this point.

764.097 -> Since this item is selected,it means that

768.089 -> it must be taking 4 weight so whatever weight we're left with which is 3

773.18 -> and whatever 2 items we are left that is where we're gonna end up next.

776.063 -> So that's this point.So item with weight 4 and

779.093 -> value 5 is selected. Then we check where's this guy coming from.This guy is not

783.094 -> coming from the top.

785.002 -> So this guy,this particular row also must be selected so the item with

789.089 -> weight 3 and value 4 is also selected.

793.082 -> So again now that this time is selected

797.008 -> and the weight of this,the weight of this

800.097 -> item is 3 so we go up and go 3 steps back

804.074 -> and reach this point. As soon as we reach a point

808.779 -> where the weight is 0 we are done. So basically

812.41 -> these 2 items are our selected items and the total value here is 9

816.011 -> and total weight is 7 so total weight is less than equal to

820.071 -> the sum of the weight is less than equal to total weight and the value is

824.028 -> maximum. Next let's look at the formula for this

827.091 -> problem.So here i is my column and j is my,

832.046 -> i is my row and j is my column so if

838.459 -> j which is my weight

840.16 -> is less then weight of i

844.055 -> so weight of item i,it means that

848.073 -> i cannot be contributing towards j so our T of

853.047 -> i,j

856.081 -> will be whatever the best we can do without

860.097 -> i which is i-1 and

864.003 -> j as

868.072 -> it means that weight of

872.649 -> I is less than equal to j then

876.079 -> T[i][j] will be

881.069 -> max of

884.17 -> either if item i is included

888.009 -> then value of i plus

892.63 -> t of i minus

898.569 -> 1 and j minus

902.339 -> weight of i so if the,

905.67 -> if item i is included then value of i plus

908.709 -> excluding this item and subtracting

912.509 -> this,the weight of this item from total weight whatever we are left with so that's T[i-1]

917.42 -> [j-wt[i])

918.061 -> so maximum of this or without including this item altogether the

923.056 -> best we can do

924.067 -> which is T[i-1][j]

929.012 -> so pretty straight forward here if you understand the, how the 2 dimensional matrix is

933.439 -> built.

933.99 -> built.So this is all i have to talk about 0/1 knapsack problem.

938.649 -> I ask my viewer to like this video,share this video,comment on this video.

941.649 -> Check out my facebook page

943.259 -> and checkout my github link github.com/missionpeace/interview/wiki.

946.72 -> Thanks again for watching this video.

Source: https://www.youtube.com/watch?v=8LusJS5-AGo