YT YouTube2Text

YouTube2Text → Transcripts → 4.5 0/1 Knapsack - Two Methods - Dynamic Programming

4.5 0/1 Knapsack - Two Methods - Dynamic Programming — Transcript

by Abdul Bari · 4,447 words · 578 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00the problem is 01 Absa
0:02problem in this video I will explain
0:05what is 01 napsack problem and how it
0:09can be solved using dynamic programming
0:12we will understand its approach next I
0:15will show you a tabular method for
0:17solving this one then also I will show
0:20you a sets method for solving this one
0:23so there are two methods we will see
0:25both the methods first of all let us
0:27understand what the problem is
0:30here I have some four objects for each
0:33object there is some profit and there is
0:35some
0:36weight and there is a bag of capacity M
0:39that is 8 is
0:43given the objective is to fill this back
0:47with these objects so can I put them all
0:51see the capacity a is eight but the
0:54total weights of all these object is 14
0:57so all objects cannot be filled in the
0:59bag so I have to carry few of those some
1:01of those objects that is subset of those
1:03objects and I have to carry them and
1:05sell them at other place so once I sell
1:08I get this
1:09profit so I have to fill the object such
1:12that the total profit is
1:16maximized and I have to give the
1:18solution in the form of a set for each
1:21object like for example this is included
1:24and this is not included or not included
1:27like this I have to write down which one
1:28is included and not included so it means
1:31I can write down each XI either 0 or 1
1:35means the values can be 0 or 1 but not
1:38fraction so it means that the object
1:40that I'm going to carry are not
1:43divisible breakable so I cannot take the
1:47fraction of that object so this means
1:50these are some solid objects maybe a
1:52mixer or microwave1 or a router it can
1:56be something like this so which I cannot
1:59take a half of mixer in the bag so these
2:02are indivisible objects so either I
2:04should carry the whole object or don't
2:07carry it at all so I have to carry the
2:09object such that the sum of their
2:13profits should be
2:15maximized and some of
2:18their weights should be less than or
2:22equal to the capacity of the
2:24back now let us know the approach of
2:27dynamic programming for solving this one
2:29now few important things about dynamic
2:31programming dynamic programming is
2:32useful for solving optimization problem
2:35yes this demands maximum results so it's
2:37optimization problem second thing
2:41dynamic programming says that a problem
2:43should be solved in sequence of
2:45decisions so yes we can take the
2:47sequence of decisions for every object
2:49we can take shall I include or not
2:50include or not include or not so I can
2:53take decisions I can even start taking
2:55the decision from the last object also
2:57include or not include or so usually in
2:59this one we take the decision from last
3:01object towards first object so we can
3:04take sequence of decision next thing one
3:06more point that dynamic programming says
3:08that you should try all possible
3:10solutions and pick up the best one now
3:14how many possible solutions are there
3:16see when I'm writing the solution in the
3:18form of zeros and ones then it can be 0
3:210 0 means no object is included or 1 one
3:24one one means all objects are included
3:27or 0 0 0 1 means only fourth object is
3:30included or first object is
3:32included or first two objects are
3:34included like this there are many
3:36possible solutions and some of them may
3:38be feasible some may not be feasible
3:40like all objects I cannot include so
3:42anyway I should try all of them and pick
3:44up the best one so total how many
3:46solutions will be there so like four
3:49zeros and ones form if I continue so
3:51I'll be getting 2^ 4
3:54Solutions so I should try 2 power 4
3:56solution for n objects it will be 2
3:58power n solution
4:00so if I try out all then the time
4:02complexity will be 2^
4:04n this is too much time consuming so
4:08dynamic programming shows a easy method
4:10for doing the same thing we will not we
4:12will be indirectly trying all 2 power n
4:16right but not directly so we'll not
4:18spend that much time let us solve this
4:20problem using tabulation method
4:23tabulation method let us see how to fill
4:25this values and how to get the solution
4:28for this problem so for solving as the
4:31capacity of the bag is8 so I have taken
4:34the column so starting from 0 to
4:378 so this means that though the capacity
4:41is8 but we'll not consider that eight at
4:44once so we'll add weight one by one so
4:48starting from zero then let us assume
4:49weight is one weight is two and so on
4:52then rows four objects so I have taken
4:55five 0 1 2 3 4 so starting from zero so
4:58it means 1 by we will consider the
5:00object so initially we will not consider
5:02any object means we will not include any
5:04object in the bag so for filling this we
5:07have a formula so I'll show you formula
5:10after some time after filling some
5:12values so let us see first row as zero
5:16object no object is included then what
5:18will be the profit so in these boxes
5:19I'll be writing the profit so there is
5:21no profit gained when no object is
5:24included and even when the capacity of
5:27the bag is zero this are the this is the
5:29capacity these are the weights right and
5:31these are weights and the profits of the
5:33objects so these are the weights and
5:36there is zero weight is there then all
5:38these are 0 0
5:410
5:43next now we will start filling so for
5:45that I'll consider first object when I
5:48consider first object I'll take this row
5:50and I will ignore all other
5:52objects and similarly when I go to
5:55second row I'll ignore the remaining and
5:57I will take the second object as well as
6:00the first object I'll consider the first
6:02object also so it means whenever I am in
6:05I throw I will consider all the objects
6:08in the previous rows also so for the
6:11first row directly I can fill it let us
6:13see first row what is the weight of the
6:16first object two so it can be filled
6:19only when the bag capacity is two so
6:22here so what will be the profit one so
6:25fill one here then this means this is
6:28same value previous value usually we
6:31write previous value only if required
6:35then rest of the cells the capacity of
6:38the bag is increasing but how many
6:40objects I'm considering only one so I
6:42don't have anything more to fill in the
6:44bag so only that object I can fill and
6:46it will be getting profit as one one one
6:51only I'll fill the second row also right
6:55third row also in the same way then I
6:57will write down the formula let us go to
6:59second row I'm going to consider second
7:02object so as I said when I consider
7:04second object I should also include the
7:06first object so first let us look at the
7:09second object see the weight of the
7:11second object is three it can be filled
7:13in the bag only if the capacity is three
7:16so in this cell only it can be filled so
7:18what is the profit that I'll get two so
7:21put two here what about this side it
7:23will be same value same value as the
7:26previous rle then beyond this what
7:29should come here so as I said that when
7:32you are taking second object you should
7:34also consider first object so if I fill
7:37the second object also in the back total
7:39weight required is how much five so this
7:43is five and total profit will be three
7:46so both the objects can be filled when
7:48the capacity is five and the total
7:50profit will be three so here both of
7:53them can be
7:55filled right both of them I'm
7:57considering both of them so now I have
7:59have only two objects and this is giving
8:01for both the objects are filled so rest
8:03of the values will be 3 3 3 then what
8:06will be the value here so as this is two
8:08so this will also be two so I can take
8:11the previous value or this value
8:12whichever is maximum I can take the same
8:15thing now I will fill the third object
8:18also then for the fourth object I will
8:20show you the formula third object when I
8:23consider third object if you look at
8:25these the maximum weight is this one and
8:27as they are arranged in the increasing
8:29order of the weight so this is weight is
8:31four so this object can be filled in the
8:34bag only if the capacity of the bag is
8:36four so this will be included in the bag
8:40when the capacity is four so the total
8:41profit that you'll be getting is five so
8:44this is five then before that whatever
8:47the previous row values are so 2 1 and
8:51zero now Beyond this let us see see when
8:55I on the third object I should also
8:58consider first first and the second
9:00object
9:01also so if I just check them this is
9:04four and if I take these two objects it
9:08will be total six weight weight is six
9:10so these two objects I can fill if the
9:12weight is six right a if I want to fill
9:16these two then these two I can fill when
9:18the weight is
9:20seven this two I can fill if the weight
9:23is five and what will do the profit
9:25three this object itself is five right
9:29now I will consider these two six and
9:32the total weight will be six so at six
9:35it will be six only right and when I
9:38consider these two so total is seven
9:42seven and the profit is also seven so at
9:45seven the profit is seven can I include
9:48all three it will be 10 but the capacity
9:51of the bag is only eight so I cannot
9:53include all three then beyond this the
9:56value will be seven only and before this
9:58one the value will be same as this five
10:05five all right now I will show you the
10:08formula and I will fill fourth row with
10:10that formula the formula is like this if
10:14I call this table as V this table as V
10:17then V of I comma w i is the row number
10:21W is the column number is maximum
10:26of V of i- 1 that is from the previous
10:30row I should take same value means
10:32previous row value I should take this is
10:34the meaning or maximum of this one or
10:38what V of IUS 1 comma weight minus
10:43weight of an object
10:46wi plus profit of an object that you are
10:52considering now let us the follow the
10:54formula and fill all
10:57these first one 4A 1 I will fill 4A 1 so
11:02V of 4A 1 is maximum
11:07of V of 3A 1 like this is four so this
11:12will be three comma V of 3 comma weight
11:17is how much 1 minus weight of an object
11:21weight of an object is 5 1 - 5 plus
11:25profit of that object is six six
11:31now this becomes 3A
11:34-4 there is no such location so that
11:37value becomes undefined so only this
11:41value will be defined V of 3 comma 1
11:43will be defined so V of 3 comma 1 is
11:45what zero so I should take zero
11:48only there will not be any such index V
11:50of 3 comma -4 yes for that I have to
11:54take zero only so it means up to what
11:57I'll be getting negative numbers up to
11:59fifth weight up to fifth weight so till
12:02here I should fill these values as it is
12:06only so that's what I was saying that
12:09this can be considered or this can be
12:11considered in fourth so write on its
12:13value and all previous values as it is
12:16so the same thing here because there you
12:18will be getting negative so till fifth
12:21weight till fifth weight before that
12:23till before that I have filled as it is
12:25now this fifth way how to fill I will
12:28show you for this value 4A 5 V of 4A 5
12:35is maximum
12:37of V of 3 comma 5 comma V of 3 comma
12:45weight is how much five minus weight of
12:49this object is how much
12:51five plus profit of this object is how
12:54much 6 6 let us see V of 3 comma 5 3A 5
13:00is how much 5 comma V of 3A 5 - 1 5 - 5
13:060 V of 3 comma 0 3 comma 0 is 0 plus 6
13:12so which is greater 6 is greater so fill
13:15this value with six so that means this
13:18object is included
13:20here now 4A 6 I will find out V of 4A 6
13:26is maximum of V of 3A 6 comma V of 3
13:33comma weight is 6 right and the weight
13:36of the object is 5
13:38plus profit of the object is 6 so how
13:42much this is V of 3A 6 is how much 3A 6
13:46is 6 6 comma V of 3 comma 6 - 1 6 - 5
13:53that is 1 3A 1 3A 1 is how much 0 0 + 6
14:00so the answer is both are same only so
14:03take six
14:05only next value 4A 7 V of 4A 7 maximum
14:12of V of 3A 7 comma V of 3 comma weight
14:20is how much 7 so weight of the object is
14:235 7 - 5 plus profit is 6 so this is 3A 7
14:28is how much 7 comma this is V of 3A 7 -
14:335 is 2 3A 2 so 3A 2 is how much 1 + 6 so
14:39this is 1 + 6 so this is 7 only both I
14:43am getting s or 7 so they are same only
14:46take
14:47seven V of 4A 8 4A 8 is maximum
14:54of V of
15:003A 8 comma V of 3 comma weight is 8
15:05minus the weight of an object is 5 +
15:07profit is
15:096 3A 8 how much 3A 8 is 7 comma V of 3A
15:178 - 5 is 3 3 comma 3 how much 2 so this
15:21is 2 + 6 so how much this is this is
15:24seven and this is 8 so answer
15:27is8 so this is how the table is filled
15:30so I have used the formula for few cells
15:33in the last row and this can also be
15:36filled directly also without the formula
15:39let me show you how to fill this last
15:40row
15:42directly I am considering fourth object
15:45whose weight is five and the profit is
15:48six so in fifth column just write six
15:51it's profit and what to write on the
15:54cells before that same value as the
15:57previous row
15:59this what you do first then beyond this
16:04now the weight is five Beyond this the
16:06capacity of the bag is increasing so I
16:09can include other objects also so let us
16:11check other objects what I can include
16:14in the sixth column this object is
16:16definitely because its profit is maximum
16:18right 5 + 2 7 at 6 nothing will happen
16:23so take six only at seven I can consider
16:26these two these two so this is six + 1 7
16:307 then at 8 when the bag capacity eight
16:34which of the objects I can consider 5 +
16:373 8 so 6 and 2 8 so this is
16:418 so whichever objects that you can
16:44consider you just add them and in that
16:47capacity if they are fitting in you
16:48write on the Max total profit so this is
16:51a simple method for filling the cells
16:53instead of following this complex
16:55formula you can follow that method so I
16:57have shown you both
17:00solution I have to write down X1 X2 X3
17:05X4
17:07values now
17:10these now for finding these answers
17:13actually I'll be taking sequence of
17:15decision now see the decisions can be
17:17taken only if you have the data yes we
17:19have kept the data ready the formula was
17:21used for filling this data now I have to
17:24take the sequence of decision so how to
17:25solve so actually I have to know which
17:27object should be included and which
17:29should not be included in the bag so let
17:31us come with the maximum profit that is
17:34eight the last cell this eight is
17:37generated only in fourth row and in that
17:40previous row you don't find eight
17:42anywhere so it means we got this say
17:45because of including fourth object only
17:48so include the fourth
17:51object right profit is eight fourth
17:54object is included because eight is not
17:56there in previous row now what is the
17:58profit of the a a fourth object 8 minus
18:02profit is six six so this is
18:05two now remaining profit is two now
18:08check whether two is there in the third
18:11row now I have to check for the third
18:13object fourth then third then second and
18:15then one so third object two is there
18:17yes the same value two is there in the
18:20previous row also yes it is there so it
18:22means it is not because of third object
18:25so don't include third
18:27object now let us consider second object
18:30is it two there here in the second row
18:32yes two is there here is it there in the
18:35first row also no so it means this we
18:37got because of inclusion of the second
18:40object so take this as one so now
18:43remaining is 2 - 2 so
18:46zero now zero was it there in the first
18:49object so I have to consider the first
18:51object yes zero was there in the first
18:52object row was it there in the zero also
18:55yes it was there in the zero also this
18:57row also so it means don't include the
19:00object so this is the solution so it
19:03means which objects are included in the
19:04bag X2 and X4 two objects are included
19:08in the back so that is X2 is this one X4
19:11is this one so total profit will be
19:12eight so this is the maximum profit of
19:1601 napsack
19:18problem next I will solve it using sets
19:21method same problem I will solve it
19:23using set method now let us solve it
19:25using set method set method will try to
19:27find all possible possibilities and pick
19:29up the best solution so let us see how
19:32sets are generated we will prepare a set
19:35of order pay that is profit and weight
19:38so we'll start with set
19:40zero set zero in this we say no profit
19:44no weight means nothing is included in
19:47the
19:48bag then we will consider the first
19:50object that is 1 comma 2 whose profit is
19:53one and the weight is two so consider
19:55the first object so prepare s0 of 1 and
19:58and include this first object in the bag
20:01so it will be 1 comma
20:032 so actually add one comma to this
20:06order pair so we get this one now
20:08prepare set
20:10one then merge these two order Pairs and
20:14prepare this
20:15one so this means
20:18that we have considered first object so
20:21two order pairs are showing that first
20:24object is not included first object is
20:26included
20:29now let us
20:31prepare next set by considering second
20:34object so that is 2 + 3 so prepare next
20:37set that is S11 so add 2 three to these
20:41order pairs 2 + 3 so this is 2 comma 3
20:45then 2 + 3 is added so this will become
20:483 + 3A
20:525 then this is second set for the second
20:55object so when you consider second
20:58object to total four order pairs all
21:00these are merged so this is 1 2 and 2 3
21:04and this is
21:0735 this means that no object is included
21:11first object is included second object
21:13is included both objects are included
21:15four possibilities are there so all the
21:18order pairs we got then prepare S2 of 1
21:24by considering third object 5A 4 add 5A
21:274 to all all so this 5 + 4 so this is 5
21:31+ 4
21:34is 5A 4 only so 5 + 4 so this will
21:38become 6 and 6 so this is 6a 6 5 + 4 so
21:43this is 7A 7 so five is added to this
21:47and four is added to this so This become
21:498 comma 9 8 comma
21:539 now merge all these and take order
21:56pair so set three we get it as 0 0 1 2
22:03then 2
22:043 then
22:0735 then
22:1054 then 6
22:136
22:1577 now here 8 comma 99 profit is 8 and
22:21the weight is 9 so that is exceeding the
22:23capacity of the bag don't include that
22:26one
22:28so we have discarded that right now this
22:33is set three in this one if You
22:37observe this is profit this is weight
22:40profit increase weight increase then
22:42from this profit increase weight also
22:44increase profit increased and the weight
22:47also increased but here profit increase
22:49weight is decreased from 5 to 4 this is
22:52not possible profit is increasing so the
22:55weight is also increasing but weight is
22:58decreased how this possible so that's
23:00why this order pair are wrong so we have
23:03to discard any one so we will discard
23:05the one with the Lesser profit smaller
23:08profit so 1 2 3 4 5 6 now we have only
23:13six order pirs because two were invalid
23:16one was this was giving wrong values and
23:18this was exceeding the capacity of the
23:20back so cutting of this one we call it
23:23as dominance rule so with the dominance
23:25rule the value is order pair is
23:27discarded now I will consider fourth
23:30object 6A 5 I will include so I will
23:34prepare set 3 one by considering fourth
23:38objects 6A 5 so first order pair is 6
23:41comma 5 next order pair is 6 and five
23:44are added so this is 7A 7 then 6 and
23:48five are added so this is 8 comma 8 and
23:52then 6 and 5 when they are added it will
23:55become 11 comma
23:579 6 and 5 added so this become 12 comma
24:0211 and 6 5 when added to 7 and 7 so this
24:05becomes 13A
24:0912 now I have to prepare set four this
24:12is the final set must these order pairs
24:15so 0 0 is taken from here 1A 2 and 2
24:19comma 3 and 5A 4 6A 6 and 7A 7 they are
24:26coming as it is now in one 6A 5 is there
24:30so 6A 5 should come before 7A 7 so 6A 5
24:35now here again you see the profit is
24:37remaining same but the weight is
24:39reducing so this should be removed then
24:427 comma 7 is there then 8A 8 is there
24:46then remaining 11a 9 exceeding the
24:49capacity of the Back 9 11 and 12 so all
24:53three order pairs are gone so these are
24:55the order pairs I have so if You observe
24:58the method is generating all
25:02possibilities so this is one easy method
25:04of finding all possibilities so the time
25:07taken by this one is almost 2 power
25:10n now what is the solution so we have
25:13already sets now we take the sequence of
25:15decisions to solve this one now what is
25:17the maximum order of air 8A 8 so 8 comma
25:238 Now using that I will solve this one
25:26so the approach is similar like what we
25:28saw in the tabular method 8A 8 belongs
25:32to set
25:344 but 8A 8 check whether it belonged to
25:40set three in the set 3 8A 8 was not
25:43there so it doesn't belong to set three
25:46therefore fourth object is included
25:49because of that only we got 4A
25:524 now I should take an order pair 8
25:56comma 8 from this I should subtract the
25:59profit and weight of the fourth object
26:01so this is profit is six and the weight
26:03is five so the order pair is how much 2
26:07comma 3 so now I should consider 2 comma
26:103 so now this was the first one now
26:13second one 2A 3 now I have to consider
26:17third object so check whether it belongs
26:20to S3 2A 3 yes it belongs to S3 and 2A 3
26:27belongs to s 2 check whether it belongs
26:29to S2 s2a 3 is there here also it means
26:33this is not because of the third object
26:36so therefore third object is not
26:38included in the back then now next step
26:43is I will consider second object 2A 3
26:47belongs to set two for second object 2
26:49comma 3 now does it belong to set
26:521 but 2 comma 3
26:59doesn't belong to set 1 so 2 comma 3 was
27:02belonging to set 2 and 2 comma 3 doesn't
27:05belong to set 1 so therefore this is
27:07because of the second object that is
27:09included now what is the profit and
27:12weight of the second object 2A 3 so when
27:14you subtract 2 comma 3 from this one 2 -
27:172 is 0 and 3 - 3 is 0 so this gives 0a 0
27:24now first object I will consider now the
27:26step is four so 0 0 belongs to set 1 and
27:32also 0a 0 belongs to set 0 therefore
27:37first object is also not
27:40included 0a 0 belongs to S1 also s0 also
27:44it means this is obtained not because of
27:46the first object so first object is also
27:48not included then the solution is from
27:50bottom if you see 0 1 0 1 so the answer
27:55is 0 1 0 1
27:58so these two objects are included see
28:00the profit is eight so we got the same
28:03solution with the help of sets also so
28:05this is one more
28:08method that's all about 01 nsect problem
28:11leave a comment and let me know whether
28:13it was easy for you to understand so I
28:15have shown you both the steps for
28:17solving 01 naap problem right in some
28:19places we find tabulation method and
28:21some places we find the sets method

About this transcript

This page contains the full transcript of 4.5 0/1 Knapsack - Two Methods - Dynamic Programming by Abdul Bari, generated from the public captions YouTube serves with the video. The transcript has 4,447 words across 578 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to choose a caption track available on the video.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, caption language selection, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.