1 00:00:00,310 --> 00:00:03,558 Okay, guys, welcome back, this is discrete optimization, this is the 2 00:00:03,558 --> 00:00:06,330 knapsack problems. We are getting started. 3 00:00:06,330 --> 00:00:09,728 This is really easy. But we have to start from some place, so 4 00:00:09,728 --> 00:00:13,238 what we're going to do is visibly locate the one dimensional knapsack and that is 5 00:00:13,238 --> 00:00:16,802 going to introduce a bunch of concepts in optimization like you know, decision 6 00:00:16,802 --> 00:00:22,020 variables and things like that. And then, we'll also use dynamic 7 00:00:22,020 --> 00:00:25,260 programming which is a very simple techniques which works great when it 8 00:00:25,260 --> 00:00:28,554 works and, and which may be very complicated in some problems, but in this 9 00:00:28,554 --> 00:00:33,920 particular case you will see it's going to be working beautifully. 10 00:00:33,920 --> 00:00:36,650 this is the one dimensional knapsack problem, okay?. 11 00:00:36,650 --> 00:00:39,220 So, we have a set of item Alright? Okay? 12 00:00:39,220 --> 00:00:43,170 Remember this, all the stuff that, you know, Indiana Jones was trying to pick. 13 00:00:43,170 --> 00:00:47,410 And, for every one of these items, you get only two things here, okay? 14 00:00:47,410 --> 00:00:50,600 So it's not a multidimension knapsack. Only one dimension. 15 00:00:50,600 --> 00:00:52,470 So we get only the weight, okay? Wi, okay? 16 00:00:52,470 --> 00:00:56,430 That's the weight of the item that we're trying to pick. 17 00:00:56,430 --> 00:01:01,310 And then we have a value vi, okay? That's how much the, the item is worth. 18 00:01:01,310 --> 00:01:05,450 And the goal, you know, is going to be, picking up a set of items, okay? 19 00:01:05,450 --> 00:01:08,150 And they have to fit in a knapsack, so we have a capacity K. 20 00:01:08,150 --> 00:01:11,520 Capital K for the knapsack. Okay, that's what you see there. 21 00:01:11,520 --> 00:01:14,640 Okay, and so in a sense what you want to do is select you know, a set of items 22 00:01:14,640 --> 00:01:18,020 such that the weight of, the sum of the weights of these items is Lower than this 23 00:01:18,020 --> 00:01:21,452 k, and then obviously what you want to do is to maximize the value of all the items 24 00:01:21,452 --> 00:01:27,300 that you have selected, okay. So you, think of it, you have two sums 25 00:01:27,300 --> 00:01:30,382 there, the sum of the values, that's what you want to maximize, get the best value 26 00:01:30,382 --> 00:01:33,280 out of these things, and then you want also to make sure that all the items are 27 00:01:33,280 --> 00:01:38,142 fitting in the knapsack. Okay, so we have an objective function 28 00:01:38,142 --> 00:01:41,986 and then we have constraint, okay. Now, so one of the big things that we've 29 00:01:41,986 --> 00:01:45,290 seen discussed is how to model optimization problems. 30 00:01:45,290 --> 00:01:48,622 Okay, That's a key step. So you get typically what you start with 31 00:01:48,622 --> 00:01:51,380 is a informative description of a problem. 32 00:01:51,380 --> 00:01:54,330 And you have to formalize it, okay, so now that happens all the time. 33 00:01:54,330 --> 00:01:56,035 Whatever the problems that you are going to have to solve, people are 34 00:01:56,035 --> 00:01:58,070 going to tell you this is a model alright. 35 00:01:58,070 --> 00:02:01,470 You will have to talk to them and extract a model, okay. 36 00:02:01,470 --> 00:02:04,053 In many of the examples that you will see in this class they are sufficiently 37 00:02:04,053 --> 00:02:07,270 contained that, you know the transition isn't too complicated. 38 00:02:07,270 --> 00:02:09,820 In real life it may be much more complicated. 39 00:02:09,820 --> 00:02:12,604 This first thing you will have to do when you get some kind informative 40 00:02:12,604 --> 00:02:16,380 understanding of your problem is choose the decision variables. 41 00:02:16,380 --> 00:02:18,350 okay. And typically, these decisions, the 42 00:02:18,350 --> 00:02:20,990 choice is not too difficult, because at the end of the day, you are interested in 43 00:02:20,990 --> 00:02:24,318 making some decisions. And this is what the decisions variable 44 00:02:24,318 --> 00:02:26,050 are going to be. Okay? 45 00:02:26,050 --> 00:02:28,690 But sometimes, there are different ways of modeling these, you know, decision 46 00:02:28,690 --> 00:02:30,830 variables. So, you will have different kinds of 47 00:02:30,830 --> 00:02:34,340 encoding, so they may not be the first choice that you think about. 48 00:02:34,340 --> 00:02:37,785 And so there is a set of models that, you know, will be, will be modeling the same 49 00:02:37,785 --> 00:02:42,160 particular application, but may have different set of variables. 50 00:02:42,160 --> 00:02:44,240 Okay? Once you have that, okay? 51 00:02:44,240 --> 00:02:46,697 Once you have these decision variables, the next step will be looking at the 52 00:02:46,697 --> 00:02:50,140 constraints that you have. For instance, in the knapsack, the thing 53 00:02:50,140 --> 00:02:54,460 that all the items have to fit in the knapsack, you cannot exceed the capacity. 54 00:02:54,460 --> 00:02:57,233 And you will have to express these constraints in terms of the decision 55 00:02:57,233 --> 00:03:01,275 variable that you just chose, okay? So, once again, decision variables, then 56 00:03:01,275 --> 00:03:05,630 you model the constraints of the problem in terms of the, the decision variables. 57 00:03:05,630 --> 00:03:08,320 And then, afterwards you do the same thing for the objective functions. 58 00:03:08,320 --> 00:03:10,928 It's not a constraint. But, once again, it's going to be an 59 00:03:10,928 --> 00:03:15,110 expression describing the value of the eventual solutions. 60 00:03:15,110 --> 00:03:17,870 Okay, in a sense the way to think about it is this. 61 00:03:17,870 --> 00:03:21,270 The decision variable are the decision you are interested in, the constraints of 62 00:03:21,270 --> 00:03:25,190 the you know are basically defining what is a feasible solution. 63 00:03:25,190 --> 00:03:28,844 What is a solution and then the objective function telling you how good that 64 00:03:28,844 --> 00:03:33,410 particular solution is, okay. And so the result is an optimization 65 00:03:33,410 --> 00:03:35,664 model. Okay, so basically it's a clarity 66 00:03:35,664 --> 00:03:39,866 formulation of what you want to solve. It tells you what you want, doesn't tell 67 00:03:39,866 --> 00:03:43,150 us how we going to solve the problem and of course. 68 00:03:43,150 --> 00:03:45,923 One of the big goal in this class is actually finding out how we can solve 69 00:03:45,923 --> 00:03:48,730 this model. But another goal is actually how to write 70 00:03:48,730 --> 00:03:51,100 the models. Okay, so these two things are part of 71 00:03:51,100 --> 00:03:53,555 optimization. How do you write a good model and how do 72 00:03:53,555 --> 00:03:57,037 you solve a good model? Okay, and we talk about all these things 73 00:03:57,037 --> 00:03:59,846 all the time. Okay, now one of the things that is very 74 00:03:59,846 --> 00:04:03,062 nice in optimization is that there are many, many, many ways of actually writing 75 00:04:03,062 --> 00:04:06,473 these models. It depends the decision variables that 76 00:04:06,473 --> 00:04:10,240 you take The constraints how you model them and so on and so forth. 77 00:04:10,240 --> 00:04:12,823 Okay, and so we'll see a lot of problems where, oh, there is one modeling like 78 00:04:12,823 --> 00:04:15,740 this, there is another modeling like that, and so on. 79 00:04:15,740 --> 00:04:18,125 Okay. So in the knapsack problem if you go back 80 00:04:18,125 --> 00:04:20,915 to that problem, okay, the decision variables here are going to be very, very 81 00:04:20,915 --> 00:04:24,413 simple, okay. So you have a variable xi and that 82 00:04:24,413 --> 00:04:28,484 variable is going to decide if item i, okay, In the set of items that you can 83 00:04:28,484 --> 00:04:32,630 select, it's selected or not. OK? 84 00:04:32,630 --> 00:04:35,906 So Xi is going to be 1 if you select the item in the solution, or it's going to be 85 00:04:35,906 --> 00:04:40,230 0 if the item is not selected in the solution. 86 00:04:40,230 --> 00:04:41,745 OK? So, it's a, so it's a 0,1 vibor, 87 00:04:41,745 --> 00:04:48,920 sometimes we talk about a binary vibor. See, there's only 2 value 0 and 1. 88 00:04:48,920 --> 00:04:51,483 So these are the decision vibor's that we have. 89 00:04:51,483 --> 00:04:53,520 OK? So once we have you know identify this, 90 00:04:53,520 --> 00:04:56,770 identify these decision very well the next step into model the constraint and 91 00:04:56,770 --> 00:05:01,410 you see the cons, this is knapsack constraints that you see here. 92 00:05:01,410 --> 00:05:04,360 Once again you do this is a big sum for all the potential item that you can 93 00:05:04,360 --> 00:05:07,610 select OK for all the I and capital I OK, that's the set of item you can choose and 94 00:05:07,610 --> 00:05:10,710 what you see there is that you have a product and the product is multiplying 95 00:05:10,710 --> 00:05:16,865 the decision variable Xi. Weight, the weight of that particle right 96 00:05:16,865 --> 00:05:20,461 here so in a sense if you select the particle the element of this some is 97 00:05:20,461 --> 00:05:24,790 going to be Wi if you don't select it its 0. 98 00:05:24,790 --> 00:05:27,918 Essentially what you are doing is summing all the elements that you have selected 99 00:05:27,918 --> 00:05:31,830 and you make sure that they are smaller than k OK, very simple right. 100 00:05:31,830 --> 00:05:35,470 Once you did decision variable expressing this is almost trivial right And then the 101 00:05:35,470 --> 00:05:39,587 objective function is exactly the same. Instead of using the weight, you use the 102 00:05:39,587 --> 00:05:41,486 value. Of course, this is not a constraint, this 103 00:05:41,486 --> 00:05:43,595 is something that you're trying to maximize. 104 00:05:43,595 --> 00:05:47,720 Okay, so basically, once we have done it, we have an optimization model. 105 00:05:47,720 --> 00:05:50,775 Okay, and so this is the model, okay, it's very, very simple, beautiful model, 106 00:05:50,775 --> 00:05:53,620 okay. So we have the objective functions here 107 00:05:53,620 --> 00:05:57,382 that you maximize, okay, you maximize The values of the item that you select and 108 00:05:57,382 --> 00:06:01,087 then what you do is you basically make sure that all these items fit inside the, 109 00:06:01,087 --> 00:06:06,206 the, the knapsack. And then [INAUDIBLE] have to be a value 110 00:06:06,206 --> 00:06:10,112 between zero and [INAUDIBLE]. But they have to be the zero or the value 111 00:06:10,112 --> 00:06:12,882 one. One, you select the item, or you don't 112 00:06:12,882 --> 00:06:16,207 select the item, okay? So that's the [INAUDIBLE], once again, 113 00:06:16,207 --> 00:06:18,570 the clarity that I even told you to to solve it, okay? 114 00:06:18,570 --> 00:06:21,915 But it's the basis, this is vocabulary. We can talk about the problem, that we 115 00:06:21,915 --> 00:06:24,660 have a motive okay, so we know exactly where this problem is, and now we can 116 00:06:24,660 --> 00:06:28,100 discuss various solutions and we'll see that, okay? 117 00:06:28,100 --> 00:06:33,245 you see various technology for accurate sounding the, the various models. 118 00:06:33,245 --> 00:06:35,890 Okay? So one of the things that we mentioned in 119 00:06:35,890 --> 00:06:38,950 the introductory lecture is expontial growth, okay. 120 00:06:38,950 --> 00:06:41,940 When you're looking at the problem like the [INAUDIBLE] problem here you know 121 00:06:41,940 --> 00:06:45,620 they are huge number of configurations if you have many items, okay. 122 00:06:45,620 --> 00:06:49,216 So the configuration that you are looking at is all the possible, you know, 123 00:06:49,216 --> 00:06:53,800 combination of isolate this item or I don't and so on, okay. 124 00:06:53,800 --> 00:06:56,890 And so you have a very large number of all these configurations. 125 00:06:56,890 --> 00:06:59,480 That's essentially your search base, okay? 126 00:06:59,480 --> 00:07:02,808 So you will have to pick the one which satisfies the constraint, the capacity 127 00:07:02,808 --> 00:07:06,640 constraints, and maximize the objective function, okay? 128 00:07:06,640 --> 00:07:10,206 But obviously, you don't want to enumerate all these guys, why? 129 00:07:10,206 --> 00:07:14,860 Because you know they are a huge number of them. 130 00:07:14,860 --> 00:07:18,124 Of course some of them are no feasible so you have to rule them out, they exceed 131 00:07:18,124 --> 00:07:21,662 the capacity at max. But even if you look at those, you may, 132 00:07:21,662 --> 00:07:24,834 even if you look at only those that are feasible you can have a really large 133 00:07:24,834 --> 00:07:27,955 number. So if you take all the possible 134 00:07:27,955 --> 00:07:31,145 configuration the number of configurations that you have to look is 2 135 00:07:31,145 --> 00:07:36,540 to the power of the size of I. Two to the power of the number of item. 136 00:07:36,540 --> 00:07:38,220 Okay? Exponential growth, okay? 137 00:07:38,220 --> 00:07:41,140 So we can't enumerate those for very large number, okay? 138 00:07:41,140 --> 00:07:44,519 So we'll have to find a way to do better than that, okay? 139 00:07:44,519 --> 00:07:47,410 Because if you, if, if, let me just give you an example if you would try to 140 00:07:47,410 --> 00:07:51,203 enumerate them all, okay? So if it takes one millisecond, for 141 00:07:51,203 --> 00:07:56,890 instance, for testing if a configuration is feasible and finding its value, right? 142 00:07:56,890 --> 00:07:59,980 And if the number of items that you are considering is 50. 143 00:07:59,980 --> 00:08:03,510 You will need essentially this large number of centuries. 144 00:08:03,510 --> 00:08:08,090 Okay, so is like a billion centuries. Okay, and this is only 50 items. 145 00:08:08,090 --> 00:08:10,298 Right? A billion centuries that you have to wait 146 00:08:10,298 --> 00:08:14,660 for getting the ultimate solution. That's a long, long time. 147 00:08:14,660 --> 00:08:18,380 Okay, so you have to find a way to actually do this better. 148 00:08:18,380 --> 00:08:21,368 Okay, how are we going to do that today? Okay, so we are going to look at dynamic 149 00:08:21,368 --> 00:08:24,091 programming. It's very, as I said, it's very simple 150 00:08:24,091 --> 00:08:27,350 techniques. When it applies it's amazing good. 151 00:08:27,350 --> 00:08:29,574 Okay? For certain kinds of problems, this is a 152 00:08:29,574 --> 00:08:32,610 technique that you can't beat. Okay? 153 00:08:32,610 --> 00:08:35,508 it's heavily used, for instance, in computational biology, but it's also used 154 00:08:35,508 --> 00:08:37,902 in many, many different contexts, and we'll see many uses of dynamic 155 00:08:37,902 --> 00:08:42,498 programming in this class. But, once again, there are limitation to 156 00:08:42,498 --> 00:08:44,840 the, there are limitations to this technology, as well. 157 00:08:44,840 --> 00:08:46,714 Okay? But what we're going to see today is an 158 00:08:46,714 --> 00:08:51,080 introduction to dynamic programming, okay, in the context of this knapsack. 159 00:08:51,080 --> 00:08:54,520 And it's a particular example which is actually well suited, okay. 160 00:08:54,520 --> 00:08:57,250 And the basic principle is, is very simple, okay. 161 00:08:57,250 --> 00:08:59,670 There are two ideas. The one, the first one is, divide and 162 00:08:59,670 --> 00:09:02,030 conquer, okay. Very general principle in computer 163 00:09:02,030 --> 00:09:04,325 science. And the second one is what I would call 164 00:09:04,325 --> 00:09:07,460 bottom up computation. You're going to start from the bottom and 165 00:09:07,460 --> 00:09:10,680 then you're going to try to reach the goal, okay. 166 00:09:10,680 --> 00:09:13,630 And, so what are we going to do, is introduce divide and conquer, from a top 167 00:09:13,630 --> 00:09:16,930 down standpoint, and then explain why we need to go bottom up in this particular 168 00:09:16,930 --> 00:09:19,980 problem. Okay? 169 00:09:19,980 --> 00:09:22,930 So, once again, we're going to take the model, and we are going to try to solve 170 00:09:22,930 --> 00:09:26,230 it using dynamic programming, so we're going to massage those equations until we 171 00:09:26,230 --> 00:09:29,880 actually can solve this problem. Okay? 172 00:09:29,880 --> 00:09:33,820 So, the basics, we, we're going to take a basics, a set of basic conventions, okay. 173 00:09:33,820 --> 00:09:38,750 So I'm going to assume that the set of items are numbered from 1 to n, okay. 174 00:09:38,750 --> 00:09:42,930 So I is the set of numbers from 1 to n. And then this is the key here, okay. 175 00:09:42,930 --> 00:09:45,639 So, this is really important, okay. So, we're going to introduce the 176 00:09:45,639 --> 00:09:48,370 notation. Which is O k j, okay? 177 00:09:48,370 --> 00:09:52,440 And the key idea there is that O k j, okay, is the value of the optimal 178 00:09:52,440 --> 00:09:57,403 solution. If the capacity of your knapsack is k and 179 00:09:57,403 --> 00:10:03,420 if you can select the j 1st items, the 1st j items, okay? 180 00:10:03,420 --> 00:10:07,934 So, you look at the items from 1 to j. And you look at a knapsack of a capacity 181 00:10:07,934 --> 00:10:10,714 k. And what this value O j k's giving you Is 182 00:10:10,714 --> 00:10:15,830 the best solution that you can get for those configurations, okay. 183 00:10:15,830 --> 00:10:20,114 So configurations which are only looking at item 1 to j, and a capacity of the 184 00:10:20,114 --> 00:10:23,410 knapsack which is k. Okay? 185 00:10:23,410 --> 00:10:26,310 So we're going to assume that we have this, and then we're going to work with 186 00:10:26,310 --> 00:10:29,376 it, okay. And of course, what we are interested in, 187 00:10:29,376 --> 00:10:32,562 in the end is the finally the value of all capital k, which is the size the 188 00:10:32,562 --> 00:10:35,964 wheels, the, the, the full size of the knapsack and then considering all the 189 00:10:35,964 --> 00:10:39,280 item which is n. Okay? 190 00:10:39,280 --> 00:10:42,940 So, and what we're going to do is compute a value of, of, of all these O of k, j's 191 00:10:42,940 --> 00:10:47,382 in terms of other O of k, j's. You know, smaller k's, smaller j's and, 192 00:10:47,382 --> 00:10:49,240 and building these things up. okay? 193 00:10:49,240 --> 00:10:51,600 That's what we'll do at the end. Okay? 194 00:10:51,600 --> 00:10:55,128 So now, this is, this is the one slide which is the basis of everything we do in 195 00:10:55,128 --> 00:10:59,034 the rest of the lecture. And so we are going to assume that we 196 00:10:59,034 --> 00:11:02,906 have a [UNKNOWN]. Okay, which is, tell us how to solve all 197 00:11:02,906 --> 00:11:07,940 k,j minus 1 for all the value of k between 0 and capital K. 198 00:11:07,940 --> 00:11:09,826 Okay? So for all the capacities of the 199 00:11:09,826 --> 00:11:14,094 knapsack. I'm going to assume that I have the value 200 00:11:14,094 --> 00:11:18,800 from all K minus all K, J minus what okay? 201 00:11:18,800 --> 00:11:23,024 So I know that I've all the solution for all the possible of value of my nap sack 202 00:11:23,024 --> 00:11:27,919 and the J minus 1 item. Okay and the only thing that I'm going to 203 00:11:27,919 --> 00:11:32,128 do is to solve all K J assuming that I can't actually look up the value of all 204 00:11:32,128 --> 00:11:35,720 these guys. Okay? 205 00:11:35,720 --> 00:11:38,220 So I'm basically giving you a lot of information, you know. 206 00:11:38,220 --> 00:11:41,520 All the possible value for all the capacity of the knapsack. 207 00:11:41,520 --> 00:11:44,750 And then all the item between 0 and J minus 1. 208 00:11:44,750 --> 00:11:48,526 And I'm only asking you, can you give me the optimal solution if I give one more 209 00:11:48,526 --> 00:11:50,390 item? Okay? 210 00:11:50,390 --> 00:11:54,290 So I'm moving from J minus one item to J, 1 more item. 211 00:11:54,290 --> 00:11:55,685 That's all I need to do. Okay? 212 00:11:55,685 --> 00:12:00,130 So, that's the goal of this slide, okay? So what am I going to do, okay? 213 00:12:00,130 --> 00:12:03,606 There are two cases, okay, two big cases. And then in one of the cases, there are 214 00:12:03,606 --> 00:12:07,313 two other cases, okay? In the first case, is that, the weight of 215 00:12:07,313 --> 00:12:13,340 that item is greater than the capacity K of, that I have in OKJ, okay? 216 00:12:13,340 --> 00:12:16,650 If the item is bigger than the capacity that I'm looking at. 217 00:12:16,650 --> 00:12:19,112 What can I do? Well, essentially, I have to ignore that 218 00:12:19,112 --> 00:12:21,741 item. So the value of O(k, j) is going to be 219 00:12:21,741 --> 00:12:25,533 what? It's going to be simply O(k, j) minus 1 220 00:12:25,533 --> 00:12:29,980 because I can't fit this item inside and outside. 221 00:12:29,980 --> 00:12:33,255 Okay, so that's a very simple case. If I can't fit the item, I can't fit the 222 00:12:33,255 --> 00:12:36,445 item and for the value with that additional item is the same as before, 223 00:12:36,445 --> 00:12:39,750 okay? Now, the other case is when I can 224 00:12:39,750 --> 00:12:42,540 actually fit the item inside the knapsack. 225 00:12:42,540 --> 00:12:45,260 That is more interesting. Now, I have to make a decision. 226 00:12:45,260 --> 00:12:48,480 Do I take that item, or don't I take that item? 227 00:12:48,480 --> 00:12:50,494 OK? So basically I have to choose whether I 228 00:12:50,494 --> 00:12:53,272 take it or not. Now, and, essentially if I don't take it, 229 00:12:53,272 --> 00:12:57,180 that's also easy, right? The value of OKJ would be the value of 230 00:12:57,180 --> 00:12:59,220 OKJ minus one. Right? 231 00:13:01,830 --> 00:13:05,290 But you can actually take the item. When you take the item, once it's, ha-, 232 00:13:05,290 --> 00:13:08,160 what is happening? When you take the item, you're going to 233 00:13:08,160 --> 00:13:09,620 reduce the capacity. Okay? 234 00:13:09,620 --> 00:13:14,376 So the capacity now, is going to be all, it's going to be k minus the weight of 235 00:13:14,376 --> 00:13:16,700 the item. Okay? 236 00:13:16,700 --> 00:13:19,030 So it's going to be k minus wg. Okay? 237 00:13:19,030 --> 00:13:24,110 So has the item that you have, After you selected item j, okay? 238 00:13:24,110 --> 00:13:27,828 But no, no, what can we do? We can use the fact that we know all the 239 00:13:27,828 --> 00:13:31,780 values for the j minus 1 item and all the capacity, okay? 240 00:13:31,780 --> 00:13:36,248 And therefore, the value that's the best value we could get if we take the item. 241 00:13:36,248 --> 00:13:40,170 Is essentially vj, which is the value of that item j. 242 00:13:40,170 --> 00:13:45,110 And then, the best value that we could do with the capacity with, which is k-wj, 243 00:13:45,110 --> 00:13:51,230 and the j-1 [UNKNOWN] okay, the first G minus one [UNKNOWN], okay? 244 00:13:51,230 --> 00:13:55,455 And so essentially you get these two values, either I don't take the [UNKNOWN] 245 00:13:55,455 --> 00:13:59,485 and then I have okay, okay J minus one, okay or I take the [UNKNOWN] and I have 246 00:13:59,485 --> 00:14:02,704 VJ plus OK minus WK which is the weight of the 247 00:14:02,704 --> 00:14:05,800 [UNKNOWN]. 248 00:14:05,800 --> 00:14:08,464 And the J minus 1 I items. Okay, so in a sense this is the 249 00:14:08,464 --> 00:14:11,810 recourence relation that I've just, you know, shown you. 250 00:14:11,810 --> 00:14:13,030 I've just shown you. Okay? 251 00:14:13,030 --> 00:14:15,480 So if i can fit the item inside the nap sack. 252 00:14:15,480 --> 00:14:17,880 I have to do the maximum of these 2 values. 253 00:14:17,880 --> 00:14:20,300 Whether I take the item or whether I don't take the item. 254 00:14:20,300 --> 00:14:23,920 And of course, if I can't fit the item, you know, I, I just don't take it. 255 00:14:23,920 --> 00:14:26,492 Right? And so basically you have a recurrence 256 00:14:26,492 --> 00:14:30,335 relations here, which is basically defining the value of okj in terms of all 257 00:14:30,335 --> 00:14:34,290 the values with j minus 1 item. Okay. 258 00:14:34,290 --> 00:14:38,743 So that's the basic idea here of recurrence relationships, which are the 259 00:14:38,743 --> 00:14:42,260 basis of dynamic programming. Okay. 260 00:14:42,260 --> 00:14:44,735 So now we have this beautiful thing, what can we do with it, okay? 261 00:14:44,735 --> 00:14:48,505 So yeah now I have to tell you that of course, if you don't, if you have no, you 262 00:14:48,505 --> 00:14:54,216 know [INAUDIBLE] time the body is zero. Okay so now once I have this recurrence 263 00:14:54,216 --> 00:14:59,125 relationship I can write very, very simple problem which is [INAUDIBLE] okay. 264 00:14:59,125 --> 00:15:02,901 Recurrency problem which is top dog, so I can have you know, this is a C like you 265 00:15:02,901 --> 00:15:08,450 know, functions, we're actually doing that I have O, I have K, and I have J. 266 00:15:08,450 --> 00:15:11,270 And I want to compute the, that particular optimal value. 267 00:15:11,270 --> 00:15:13,418 Okay? And what I do is that if J is equal to 268 00:15:13,418 --> 00:15:16,750 zero, I have zero item, which are zero. Okay? 269 00:15:16,750 --> 00:15:19,476 Now, if the item fits inside the knapsack, I have these two cases that I 270 00:15:19,476 --> 00:15:21,380 have to do. Right? 271 00:15:21,380 --> 00:15:24,796 So I do this maximum and I call the, you know, I call, the, you know I call the 272 00:15:24,796 --> 00:15:29,863 procedure the, the function recursively. In the first case the only thing that I 273 00:15:29,863 --> 00:15:33,240 do is that I assume that I don't take the item, okay. 274 00:15:33,240 --> 00:15:39,100 Which basically means that now I'm coding recursively ok with j, with j minus 1. 275 00:15:39,100 --> 00:15:43,770 Same capacity but fewer items. Or, I take the item, then I have the vj. 276 00:15:43,770 --> 00:15:46,790 And then I call the, the function recursively. 277 00:15:46,790 --> 00:15:50,710 We've a smaller size of the item, and then, we have j minus 1 item, okay? 278 00:15:50,710 --> 00:15:53,900 So, basically, very simple recursive, you know, codes there. 279 00:15:53,900 --> 00:15:57,200 And then, obviously, if the kna-, if, if the, if the particular item doesn't fit 280 00:15:57,200 --> 00:16:00,990 inside the knapsack. I just call the value for you know O of 281 00:16:00,990 --> 00:16:04,770 k, j, which is once again, y minus O of k, j minus 1, which is the same capacity, 282 00:16:04,770 --> 00:16:09,335 but no the j minus 1, j minus 1 items only. 283 00:16:09,335 --> 00:16:12,886 Okay, so essentially every time I have this recursive relationship I can always 284 00:16:12,886 --> 00:16:16,225 write a simple recursive program like that which will actually compute the 285 00:16:16,225 --> 00:16:19,260 optimum volume. Okay? 286 00:16:19,260 --> 00:16:23,037 So very simple, very simple thing. It’s like a one to one matching between 287 00:16:23,037 --> 00:16:28,100 the equations that I’ve shown you and this simple, simple C-like function. 288 00:16:28,100 --> 00:16:30,226 Okay? Now is it, is this any good? 289 00:16:30,226 --> 00:16:32,792 Okay? So the question, the question I'm asking 290 00:16:32,792 --> 00:16:36,530 you here is simple, right? If I write this program, is it going to 291 00:16:36,530 --> 00:16:38,905 be good? Is it going to be exponential time, or is 292 00:16:38,905 --> 00:16:41,760 it going to be low polynomial time? What is it? 293 00:16:41,760 --> 00:16:44,110 Alright? So let me give you an analogy, okay? 294 00:16:44,110 --> 00:16:47,594 So assume that I want to solve a problem which computes all the Fibonacci numbers, 295 00:16:47,594 --> 00:16:50,344 okay? So this is a recursive function, which is 296 00:16:50,344 --> 00:16:55,080 very, very similar to the, to what I just wrote for the knapsack problem, right? 297 00:16:55,080 --> 00:16:58,272 So if I have a fibonaci number and if I want to compute the volume of, the 298 00:16:58,272 --> 00:17:02,295 fibonaci of n. So if N is equal to 0 and 1 I would 299 00:17:02,295 --> 00:17:05,890 return 1. Otherwise I would compute these 2 things. 300 00:17:05,890 --> 00:17:07,890 I would compute fibonaci n mins 1. I would compute fibonaci of N minus 2. 301 00:17:07,890 --> 00:17:13,320 And I would sum these 2 guys. Okay. 302 00:17:13,320 --> 00:17:15,460 And I would return the result. Okay? 303 00:17:15,460 --> 00:17:18,940 Now, is that program any good? Okay, so this program is a little bit 304 00:17:18,940 --> 00:17:22,288 simpler, because we have only, you know, we have only one number here in the 305 00:17:22,288 --> 00:17:26,984 recurrence, in a sense, okay? But, so, so it's easier to find out what 306 00:17:26,984 --> 00:17:30,176 is good or not, okay? So, because if you start with n, okay, 307 00:17:30,176 --> 00:17:34,540 how many subproblems do you have? You have two subproblems to tackle, okay? 308 00:17:34,540 --> 00:17:38,310 So you have Fibonacci of n minus 2, and Fibonacci of n minus 1, okay? 309 00:17:38,310 --> 00:17:40,800 So when you take one of these subproblems, let's say. 310 00:17:40,800 --> 00:17:43,200 fibonacci over minus 2. And you try to solve it. 311 00:17:43,200 --> 00:17:45,955 What are you going to do? You are going to create another 2 312 00:17:45,955 --> 00:17:49,394 problems okay. And then these 2 problems are going to 313 00:17:49,394 --> 00:17:53,162 great another 2 problems okay? And it's the same thing for you know the 314 00:17:53,162 --> 00:17:57,710 left, the right of the recurssion that guy is going to create 2 sub problems. 315 00:17:57,710 --> 00:18:00,680 Which are also going to create you know, every one of them are going to create two 316 00:18:00,680 --> 00:18:04,260 separate problems. So what you see here is what? 317 00:18:04,260 --> 00:18:06,080 It's exponential growth. Okay? 318 00:18:06,080 --> 00:18:09,200 So, you basically see that this very simple program, very naive program is the 319 00:18:09,200 --> 00:18:12,272 syntax, every time you go into one level of the recursion you're doubling the 320 00:18:12,272 --> 00:18:16,743 number of nodes, okay? Now, it's completely unnecessary this 321 00:18:16,743 --> 00:18:17,860 way. Why? 322 00:18:17,860 --> 00:18:20,836 Why is it completely unnecessary to actually double these large number of 323 00:18:20,836 --> 00:18:24,123 nodes? Well, when you try to solve Fibonacci of 324 00:18:24,123 --> 00:18:27,240 n minus 1, what is it that you're going to do? 325 00:18:27,240 --> 00:18:32,890 Well, you're going to solve Fibonacci of n minus 3 and Fibonacci of n minus 2. 326 00:18:32,890 --> 00:18:36,150 But, which you just computed. Fibonacci of N minus two. 327 00:18:36,150 --> 00:18:39,600 So there are plenty of problems that are really the same everywhere. 328 00:18:39,600 --> 00:18:41,690 OK? But the stupid implementation, in a 329 00:18:41,690 --> 00:18:44,706 sense, doesn't see that, and recompute them all over, and you get this 330 00:18:44,706 --> 00:18:47,420 exponential growth. OK? 331 00:18:47,420 --> 00:18:50,830 So the way to think about dynamic programming is that instead of computing 332 00:18:50,830 --> 00:18:55,494 this function top-down, we are going to basically compute it bottom-up. 333 00:18:55,494 --> 00:18:57,579 OK? And that will make sure that we never, 334 00:18:57,579 --> 00:19:02,370 never, never solve a sub-problem twice. Okay, so that's the key idea. 335 00:19:02,370 --> 00:19:05,570 Okay, so it's going to be the same recurrence relationship, the same formula 336 00:19:05,570 --> 00:19:10,240 but instead of computing them top down, we're going to compute them bottom up. 337 00:19:10,240 --> 00:19:13,216 And that's going to basically, you know, handle the fact that, handle this 338 00:19:13,216 --> 00:19:16,576 exponential growth that we get because we recompute many, many, many times the same 339 00:19:16,576 --> 00:19:19,792 things. Okay. 340 00:19:19,792 --> 00:19:22,598 So, so what these equations, you know, so, so the way we're going to look at 341 00:19:22,598 --> 00:19:26,452 these equations bottom up is very simple. All right, so we're going to start with 342 00:19:26,452 --> 00:19:29,320 zero item. What is the best we can do if we have 343 00:19:29,320 --> 00:19:31,530 zero item to work with? Okay. 344 00:19:31,530 --> 00:19:33,220 And that's going to be pretty simple, right? 345 00:19:33,220 --> 00:19:35,760 And then we're going to do the same thing with one item. 346 00:19:35,760 --> 00:19:38,690 And then, what is the best that we can do with two items? 347 00:19:38,690 --> 00:19:41,610 And then, what is the best we can do with three item, and so on and so forth. 348 00:19:41,610 --> 00:19:43,692 Okay? So we are, basically, going to grow, 349 00:19:43,692 --> 00:19:46,932 we're going to do this induction essentially on the number of items, okay, 350 00:19:46,932 --> 00:19:49,320 one at a time. Okay. 351 00:19:49,320 --> 00:19:51,270 So, how are we going to do this induction? 352 00:19:51,270 --> 00:19:54,503 The best way to think about dynamic programming in general is to look at it 353 00:19:54,503 --> 00:19:57,276 as a table. So we're going to build A huge table, 354 00:19:57,276 --> 00:20:00,096 okay, hopefully it's going to be resonably small, but we are looking at a 355 00:20:00,096 --> 00:20:04,250 big table, okay. So, and this table is going to basically 356 00:20:04,250 --> 00:20:08,536 look at the induction step by step. We are going to look at the first column 357 00:20:08,536 --> 00:20:10,854 and that's, that column is going to be, what can I do with zero item, and the 358 00:20:10,854 --> 00:20:13,400 next column is going to be, what can I do with one item, the following column, what 359 00:20:13,400 --> 00:20:17,035 can I do with two items and so on and so forth. 360 00:20:17,035 --> 00:20:20,040 Okay? So, everyone of these columns is 361 00:20:20,040 --> 00:20:25,450 basically going to add one more item. To the, the selection that we can wait. 362 00:20:25,450 --> 00:20:28,290 And, so that's going to be the, that's going to be the x axis. 363 00:20:28,290 --> 00:20:32,820 The y axis is going to be the capacity of that particular knapsack, okay. 364 00:20:32,820 --> 00:20:36,348 So, when I look at the first column, what I'm basically asking is what can I do 365 00:20:36,348 --> 00:20:39,570 with 0 items, okay? And that's easy, right? 366 00:20:39,570 --> 00:20:40,860 So, what can I do, is nothing. So. 367 00:20:40,860 --> 00:20:45,110 So the value that you see there is the best possible thing that I can get. 368 00:20:45,110 --> 00:20:50,600 If I can pay with 0 item and, let's say, my capacity of the knapsack is 7, okay? 369 00:20:50,600 --> 00:20:52,570 So that's the value that you find over there, okay? 370 00:20:52,570 --> 00:20:57,898 So, 0 item, capacity is 7, I get 0, okay? Now, We start getting a little bit more 371 00:20:57,898 --> 00:21:01,160 interesting here. We can select one item, the first item. 372 00:21:01,160 --> 00:21:04,136 And what you see over there is the value of that item, 5; is the weight of that 373 00:21:04,136 --> 00:21:07,230 item, 4, okay? So, what is going to be that column? 374 00:21:07,230 --> 00:21:09,170 That column is going to be very simple, okay? 375 00:21:09,170 --> 00:21:14,065 If I can't fit the item, I get a value 0. If I can fit the item, I get the value 376 00:21:14,065 --> 00:21:16,544 five. And that's what you see in that column, 377 00:21:16,544 --> 00:21:19,230 okay? Zero until the capacity is four. 378 00:21:19,230 --> 00:21:24,120 And when the capacity is four and, and, and above I get the value five, okay? 379 00:21:24,120 --> 00:21:28,200 Two item is, is still interesting but very easy to do right? 380 00:21:28,200 --> 00:21:31,052 So what you're going to do is basically look at You know, what is the first time 381 00:21:31,052 --> 00:21:33,858 we can put one of the items, okay, and then, you know, if the, if, if there is 382 00:21:33,858 --> 00:21:36,480 only one item you're going to take out one, if there are two with the same 383 00:21:36,480 --> 00:21:42,180 value, you're going to choose the one which has the highest value. 384 00:21:42,180 --> 00:21:45,169 And then you're going to continue doing that until you have, you can fit both 385 00:21:45,169 --> 00:21:49,260 items, and you have the sum of the, of the values of these two items. 386 00:21:49,260 --> 00:21:52,396 Okay, so what we see here is that we are considering a new item which has a value 387 00:21:52,396 --> 00:21:54,770 6 And a weight of five. OK? 388 00:21:54,770 --> 00:21:58,175 So the first thing that you're going to see in this column is a bunch of zeros. 389 00:21:58,175 --> 00:22:00,930 OK? Then, when the capacity is full, we know 390 00:22:00,930 --> 00:22:05,280 that we can put the first item, so this is going to be the value five. 391 00:22:05,280 --> 00:22:08,480 When we have value five, six, and so on, until the very last value, we are going 392 00:22:08,480 --> 00:22:11,430 to put the second item, because the second item is more valuable, it is a 393 00:22:11,430 --> 00:22:14,680 high weight But it's, it's more valuable so you see a bunch of six over there and 394 00:22:14,680 --> 00:22:17,780 this last value here is when you can actually put both items because the sum 395 00:22:17,780 --> 00:22:20,980 of these two things is going to be nine and the capacity of the knapsack here is 396 00:22:20,980 --> 00:22:27,274 nine. So, you have a total value here of 11 397 00:22:27,274 --> 00:22:30,700 because you can fit both items, you sum the values. 398 00:22:30,700 --> 00:22:32,580 Okay? So, so far very easy. 399 00:22:32,580 --> 00:22:34,440 You know, we haven't done really anything. 400 00:22:34,440 --> 00:22:37,870 So, the next column is more interesting. That's where we are basically going to 401 00:22:37,870 --> 00:22:40,868 use these recurring relation. And the fact that we can select an item 402 00:22:40,868 --> 00:22:43,534 or not. And, we are also going to use the fact 403 00:22:43,534 --> 00:22:46,652 that wow! At this point, we have already compute 404 00:22:46,652 --> 00:22:50,216 the value of all the possible combinations of the capacity of the 405 00:22:50,216 --> 00:22:53,760 knapsack and 2 items. Right? 406 00:22:53,760 --> 00:22:56,370 So we know, in a sense, what this column is giving you, right? 407 00:22:56,370 --> 00:22:59,954 This beautiful column here is giving you the best you can do if you can have two 408 00:22:59,954 --> 00:23:03,680 items and a particular capacity for the knapsack. 409 00:23:03,680 --> 00:23:07,220 So essentially now, we can, you can view this as a look-up table. 410 00:23:07,220 --> 00:23:09,860 When we compute this column, we are going to ask questions, and we're 411 00:23:09,860 --> 00:23:14,140 going to get the answer, because we have actually computed these values already. 412 00:23:14,140 --> 00:23:15,860 Okay? So let's see what we do. 413 00:23:15,860 --> 00:23:18,085 At the beginning, okay, so we have this new item now. 414 00:23:18,085 --> 00:23:20,072 Okay? That new item is a value three and a 415 00:23:20,072 --> 00:23:21,640 weight of two. Okay? 416 00:23:21,640 --> 00:23:24,076 So what we're going to do is, you know, abuthly as a, you know, as long as we 417 00:23:24,076 --> 00:23:27,830 don't have enough capacity for any one of them we're going to get zeroth. 418 00:23:27,830 --> 00:23:30,542 Okay? When we get a capacity of two, you know, 419 00:23:30,542 --> 00:23:33,486 we know that the new guys, you know, this guy is only a, a weight of two, so we can 420 00:23:33,486 --> 00:23:36,760 put it in. So we get a value of three, for these two 421 00:23:36,760 --> 00:23:39,600 things. And now we come to the point where you 422 00:23:39,600 --> 00:23:43,659 know we are a capacity of four. And now there are at least two items that 423 00:23:43,659 --> 00:23:44,840 we can fit. Okay? 424 00:23:44,840 --> 00:23:47,770 So, what are going to do? So, this is where for the first time you 425 00:23:47,770 --> 00:23:50,200 are going to see the recurrence relationship. 426 00:23:50,200 --> 00:23:52,360 Right? So what you see is that there are always 427 00:23:52,360 --> 00:23:56,630 two possibilities, right? So you can look on your left, okay? 428 00:23:56,630 --> 00:24:00,351 So if you look on your left, it's basically the decision of not taking the, 429 00:24:00,351 --> 00:24:04,879 not taking the knapsack, okay? So when, and so, not taking the, the, the 430 00:24:04,879 --> 00:24:07,330 new item, okay? So, you're basically saying, I'm not 431 00:24:07,330 --> 00:24:10,360 going to take this item. So, the best value that I can do is what? 432 00:24:10,360 --> 00:24:13,447 Well, is looking at the column which, with the value of the cell which is here 433 00:24:13,447 --> 00:24:17,520 which has the same capacity as the capacity we're looking at, okay. 434 00:24:17,520 --> 00:24:21,350 But is using, is not using the just, the item that we're considering now. 435 00:24:21,350 --> 00:24:24,220 It's using all the other ones, okay. And so, in this particular case we can 436 00:24:24,220 --> 00:24:26,550 decide, oh I am not going to select the new item. 437 00:24:26,550 --> 00:24:28,560 And therefore the value is going to be five. 438 00:24:28,560 --> 00:24:31,470 Or I can decide I'm going to select this item. 439 00:24:31,470 --> 00:24:35,187 And then what I'm going to do is look at the table, okay, of what I can do with 440 00:24:35,187 --> 00:24:39,320 all the other items, but now a lower capacity. 441 00:24:39,320 --> 00:24:41,540 Because I took some capacity of the knapsack. 442 00:24:41,540 --> 00:24:43,730 In this particular case, this guy is a weight of two. 443 00:24:43,730 --> 00:24:45,850 So I'm going to look at that particular cell here. 444 00:24:45,850 --> 00:24:49,379 And that cell is a zero, okay? So I'm going to say, I can take the not, 445 00:24:49,379 --> 00:24:52,770 I can take the new item, okay, which is a value 3, okay? 446 00:24:52,770 --> 00:24:56,172 And, and then, with the other items and the capacity that I have, which is 2, I 447 00:24:56,172 --> 00:24:59,720 can't do anything. So the total value's going to be 2. 448 00:24:59,720 --> 00:25:02,740 Or, I can decide not to take the item, and then the total value is 5. 449 00:25:02,740 --> 00:25:05,740 So in this particular case, the best decision is not to take the item. 450 00:25:05,740 --> 00:25:07,410 I get a 5. Okay? 451 00:25:07,410 --> 00:25:09,850 The next, you know, the, the reasoning for the next cell is the same thing, 452 00:25:09,850 --> 00:25:12,400 except that I select another item, which is 6. 453 00:25:12,400 --> 00:25:14,643 But once again. What I did was looking at my left and 454 00:25:14,643 --> 00:25:18,374 take the value of that cell. So, in a sense the cell just next to the 455 00:25:18,374 --> 00:25:23,405 one that you're computing, you have to do at least as good as that. 456 00:25:23,405 --> 00:25:25,895 Okay? So now this item here is very 457 00:25:25,895 --> 00:25:29,945 interesting, 6, okay? So we have a capacity of 6, and we are 458 00:25:29,945 --> 00:25:34,108 wondering if we take this item or not. Obviously, we know that because when we 459 00:25:34,108 --> 00:25:37,500 look at the, the left, we have at least the value of 6 that. 460 00:25:37,500 --> 00:25:41,190 We'll do a [UNKNOWN] six, okay? So but can we do better, okay? 461 00:25:41,190 --> 00:25:43,896 So once again, there are two decisions so you don't take the item, you get a value 462 00:25:43,896 --> 00:25:47,566 of six or you take the item. If you take the item, you take a capacity 463 00:25:47,566 --> 00:25:50,842 of two, now you have to look at what you can do with essentially, all, you know 464 00:25:50,842 --> 00:25:54,810 the first two items and a capacity of four, okay? 465 00:25:54,810 --> 00:25:58,779 So, this is essentially all four, two, right, so that when we were reasoning 466 00:25:58,779 --> 00:26:03,690 about the recurrence relationship. In this particular case, you get the 467 00:26:03,690 --> 00:26:04,770 value five. Okay. 468 00:26:04,770 --> 00:26:08,098 five, five if you basically took this capacity, and now you have a value of the 469 00:26:08,098 --> 00:26:14,300 item that we just selected, which is two. So you get a value here, which is three, 470 00:26:14,300 --> 00:26:18,828 the value three, sorry. So we get the value three plus the value 471 00:26:18,828 --> 00:26:21,480 five, and then we get the value eight there. 472 00:26:21,480 --> 00:26:23,444 Okay? And that's what you see on the sets, and 473 00:26:23,444 --> 00:26:27,388 the last set here, is, is going to be 11. Okay, so, basically, all these sets here 474 00:26:27,388 --> 00:26:29,400 are now taking the item. Okay? 475 00:26:29,400 --> 00:26:32,648 So in a sense what I've shown you here is that you can use this recurrent 476 00:26:32,648 --> 00:26:38,080 relationship by looking at the, at the column which is just on your left. 477 00:26:38,080 --> 00:26:40,852 Okay if you don't think the eye can devalue just on your left otherwise, it's 478 00:26:40,852 --> 00:26:44,356 just a little bit upwards. Okay, by the size of the item and you see 479 00:26:44,356 --> 00:26:47,695 the value which is there and you are value of the item that's what, that's the 480 00:26:47,695 --> 00:26:52,094 column that you see okay. And of course we can continue that You 481 00:26:52,094 --> 00:26:55,496 can continue to do that for all the possible items so in this particular case 482 00:26:55,496 --> 00:26:58,790 we have only three items OK, and so we have done, OK.Now what we know at this 483 00:26:58,790 --> 00:27:02,192 point is that this, if this is the food capacity of knapsack these are all the 484 00:27:02,192 --> 00:27:09,450 items that I can take that the best that I could ever do is over there OK. 485 00:27:09,450 --> 00:27:12,550 Its the value 11. So I know that the optimal value to my 486 00:27:12,550 --> 00:27:16,210 knapsack problem is here. But I don't have the decisions, right? 487 00:27:16,210 --> 00:27:20,410 So this point, the only thing that I have is, I have this beautiful knapsack, okay? 488 00:27:20,410 --> 00:27:25,230 And the n-, well, I have this beautiful objective value; I know I can do 11. 489 00:27:25,230 --> 00:27:28,330 What you're telling Andrew, yes, yes, yes, you can do 11, but he has no clue, 490 00:27:28,330 --> 00:27:32,368 which items he has to pick, right? So the thing that we going to do now, is 491 00:27:32,368 --> 00:27:35,748 essentially finding from that popular value, in the table, which item we have 492 00:27:35,748 --> 00:27:39,678 to pick. And there is a beautiful thing, which is 493 00:27:39,678 --> 00:27:42,730 essentially Tracing back the algorithm, okay. 494 00:27:42,730 --> 00:27:46,060 And so what we do is we look at this value, okay. 495 00:27:46,060 --> 00:27:49,656 If this value, so we look at this value and we look at the value which is on its 496 00:27:49,656 --> 00:27:52,755 left again. Okay, so if these two values are the 497 00:27:52,755 --> 00:27:56,125 same, what does it mean? It means that, well, you know, you don't 498 00:27:56,125 --> 00:27:59,820 take the item. Because essentially, that value was 11. 499 00:27:59,820 --> 00:28:03,580 We bought the item, and you still have a value which is 11 there with the item. 500 00:28:03,580 --> 00:28:06,860 So you can just not take the item, okay? And now, you get back there. 501 00:28:06,860 --> 00:28:10,560 So you know that we don't need to take item number three. 502 00:28:10,560 --> 00:28:13,189 Okay? So we go back to this point here, okay, 503 00:28:13,189 --> 00:28:17,467 and we say, oh, you know, is the value on my left, okay, as the same value as my 504 00:28:17,467 --> 00:28:20,843 south? And it's not the case in this particular 505 00:28:20,843 --> 00:28:21,980 case. Okay. 506 00:28:21,980 --> 00:28:24,530 So you say ooh, but that means that I picked an item. 507 00:28:24,530 --> 00:28:27,150 Okay. So you can, so when you trace back you 508 00:28:27,150 --> 00:28:30,400 look at the capacity of that item. Okay. 509 00:28:30,400 --> 00:28:33,270 Which is item 2. And you trace back. 510 00:28:33,270 --> 00:28:36,570 Okay. So that item took a capacity of 5. 511 00:28:36,570 --> 00:28:37,940 Okay. And you get back to this cell. 512 00:28:37,940 --> 00:28:41,170 And this cell has a value of 5. OK? 513 00:28:41,170 --> 00:28:45,230 So once again, for that cell, you look at that cell on it's left, and you see 0. 514 00:28:45,230 --> 00:28:49,508 Ooh, that means that you pick up that item, you pick up item 1, and then you go 515 00:28:49,508 --> 00:28:55,060 back to the top left most cell. And that's know when, that's essentially 516 00:28:55,060 --> 00:28:58,830 when the algorithm, the tracing back is completed. 517 00:28:58,830 --> 00:29:01,690 So what this means, here, is that you're going to have this kind of jagged line, 518 00:29:01,690 --> 00:29:05,374 in general, in your table. And when you go straight, it basically 519 00:29:05,374 --> 00:29:10,402 means that you don't take the item. When you go up that basically means that 520 00:29:10,402 --> 00:29:14,328 you take the item, okay? And you can alternate, or I take the 521 00:29:14,328 --> 00:29:17,500 item, I don't take the item, I take the item, I take the item, and so on and so 522 00:29:17,500 --> 00:29:19,960 forth. Okay? 523 00:29:19,960 --> 00:29:23,432 And that's so you can, from the table, and the optimal value that you have on 524 00:29:23,432 --> 00:29:26,960 this, you know, bottom corner, you can recompute the value of, you can which 525 00:29:26,960 --> 00:29:31,580 item you have selected or not. Okay. 526 00:29:31,580 --> 00:29:34,874 So, essentially in this particular case we take item 1 and 2 and we have the 527 00:29:34,874 --> 00:29:38,066 optimal solutions. Not only the opt..., you know, in 528 00:29:38,066 --> 00:29:42,150 addition to the optimal values that we had when, when doing the forward phase. 529 00:29:42,150 --> 00:29:44,520 Okay. So, let's look at the bigger example now. 530 00:29:44,520 --> 00:29:46,820 Well, not much bigger, only four items. Okay. 531 00:29:46,820 --> 00:29:50,060 Capacity of the knapsack is 7. These are the value of all the items. 532 00:29:50,060 --> 00:29:52,730 This is the weight of all the items. So, we build this table. 533 00:29:52,730 --> 00:29:54,400 The table is a little bit bigger than before. 534 00:29:54,400 --> 00:29:58,738 We have these 4 items, no, okay? I select item I say 0 item, the 1st, the 535 00:29:58,738 --> 00:30:02,950 2nd, 3rd, the 4th, okay? And the capacity of my knapsack now is 536 00:30:02,950 --> 00:30:06,470 between 0 and 7. Okay, so I'm letting you actually do this 537 00:30:06,470 --> 00:30:08,690 on your own. Okay, so you can compute it. 538 00:30:08,690 --> 00:30:11,690 So, I'm going to freeze For, you know, ten seconds, okay. 539 00:30:11,690 --> 00:30:14,337 So, you can freeze the screen. You know, you can freeze the video your, 540 00:30:14,337 --> 00:30:16,290 yourself and then you can fill this table. 541 00:30:16,290 --> 00:30:18,550 Okay, not right on your screen, right. But you can do that. 542 00:30:20,310 --> 00:30:22,630 Okay, so I'm assuming that you've done it, okay. 543 00:30:22,630 --> 00:30:24,680 So this is the result that you should get, okay. 544 00:30:24,680 --> 00:30:27,800 So, when we fill the table using this recurrent relationship, and the optimal 545 00:30:27,800 --> 00:30:30,960 value is there. It's 44, okay. 546 00:30:30,960 --> 00:30:33,510 So, how do we trace back in this particular case? 547 00:30:33,510 --> 00:30:35,904 We're going to do exactly the thing that we have done before, we look at the cell 548 00:30:35,904 --> 00:30:39,800 just next to it. Ooh, it's 42, it's not 44, okay? 549 00:30:39,800 --> 00:30:42,548 So, therefore, we know that we took item 4, okay? 550 00:30:42,548 --> 00:30:47,370 So item 4 has a value of 028 and a weight of 5, okay. 551 00:30:47,370 --> 00:30:51,150 So we decrease the capacity of the knapsack by 5, okay, and we look at that 552 00:30:51,150 --> 00:30:54,867 set over there, of loosely 28 and 16 should be 44, that's what you, we are 553 00:30:54,867 --> 00:31:00,600 reassured, okay, we computed right. And the capacity of the knapsack is 2 554 00:31:00,600 --> 00:31:02,880 now, okay? So you gotta look at that [INAUDIBLE]. 555 00:31:02,880 --> 00:31:04,870 Look at the, you look at this left, it's 16. 556 00:31:04,870 --> 00:31:06,482 So we know that we've haven't taken item 3. 557 00:31:06,482 --> 00:31:09,515 It's 16 again. We haven't taken item 2. 558 00:31:09,515 --> 00:31:11,250 [INAUDIBLE], in this particular case is zero. 559 00:31:11,250 --> 00:31:14,500 So you go up, okay? Which basically means you take item one. 560 00:31:14,500 --> 00:31:17,910 And know we are at the bottom left or the top left hand corner. 561 00:31:17,910 --> 00:31:21,270 And we know we are done, okay? So in this particular case, we took item 562 00:31:21,270 --> 00:31:24,806 4 and we took item 1, okay? And this is the ultimate solution. 563 00:31:24,806 --> 00:31:27,875 you know, 44. We can fit inside the knapsack, and we 564 00:31:27,875 --> 00:31:30,250 have the best optimal value. Okay? 565 00:31:30,250 --> 00:31:32,930 Now you have seen how dynamic programming is working, okay? 566 00:31:32,930 --> 00:31:35,675 So one of things that we have seen is that if you compute this thing top down 567 00:31:35,675 --> 00:31:38,645 you're going to repeat, repeat, repeat again, solving the same problems over and 568 00:31:38,645 --> 00:31:41,500 over again. Okay? 569 00:31:41,500 --> 00:31:45,902 So, by doing this table computation, this basically dynamic program, we avoid doing 570 00:31:45,902 --> 00:31:48,950 that. We will never recompute the same thing 571 00:31:48,950 --> 00:31:51,770 twice, okay? But are we polynomial? 572 00:31:51,770 --> 00:31:54,115 What is the complexity of the algorithm that I've shown you? 573 00:31:54,115 --> 00:31:56,795 Okay? Well, it's basically the time to fill 574 00:31:56,795 --> 00:31:59,990 this table, okay? So we have two axes, x and y. 575 00:31:59,990 --> 00:32:02,810 You know, on the x [INAUDIBLE] axis, you know? 576 00:32:02,810 --> 00:32:05,260 What we have is the number of an item, okay? 577 00:32:05,260 --> 00:32:09,090 So on the y axis, what we have is the capacity of the knapsack, okay? 578 00:32:09,090 --> 00:32:11,640 So it's basically an algorithm which we'll take, you know? 579 00:32:11,640 --> 00:32:14,750 The capacity of the knapsack times the number of item, okay? 580 00:32:14,750 --> 00:32:18,120 Wow. This is an MP hard problem. 581 00:32:18,120 --> 00:32:22,230 An MP complete, well, MP hard problem in this case, because we are optimizing. 582 00:32:22,230 --> 00:32:28,780 And we are solving it in that time? Does that mean that this is polynomial? 583 00:32:28,780 --> 00:32:32,146 In which case, we would have solved the most, you know, interesting problems in 584 00:32:32,146 --> 00:32:35,902 computer science. Well, the question that you have to ask 585 00:32:35,902 --> 00:32:40,056 you is how can you represent K, the value K, the capacity of the knapsack on a 586 00:32:40,056 --> 00:32:44,185 computer, okay? So if you try to represent K on a 587 00:32:44,185 --> 00:32:48,420 computer, you know, the way the computers are representing this. 588 00:32:48,420 --> 00:32:52,600 Is by using this memory words and this bits representation, okay? 589 00:32:52,600 --> 00:32:56,120 And, essentially, to represent K on a computer, okay, using, you know, two's 590 00:32:56,120 --> 00:32:59,750 complement notation for instance, you would l-, you would need, essentially, 591 00:32:59,750 --> 00:33:04,034 log(K) bits. So, in a sense, when you look at log(K) 592 00:33:04,034 --> 00:33:07,060 bit, that's the size of your input for K, okay? 593 00:33:07,060 --> 00:33:11,020 And you look at the complexity of the algorithm, this is obviously exponential 594 00:33:11,020 --> 00:33:15,282 in the size of the input, okay? So what, what we have seen here is that 595 00:33:15,282 --> 00:33:19,660 if K is small essentially, This is going to be a very efficient algorithm. 596 00:33:19,660 --> 00:33:23,430 So, and that's what we call, essentially, pseudo polynomial algorithm. 597 00:33:23,430 --> 00:33:26,170 They are going to be very well if k is small. 598 00:33:26,170 --> 00:33:29,281 If k is large, essentially the algorithm is going to take, the table is going to 599 00:33:29,281 --> 00:33:33,330 get big, and essentially, it's going to take a long time to compute. 600 00:33:33,330 --> 00:33:36,775 Okay, so essentially, a polynomial algorithm is not a polynomial algorithm, 601 00:33:36,775 --> 00:33:41,430 but it behave like a polynomial algorithm when the numbers are small Okay? 602 00:33:41,430 --> 00:33:44,664 And so we haven't, you know, we haven't solved the most open problem in computer 603 00:33:44,664 --> 00:33:47,210 science, unfortunately. Okay? 604 00:33:47,210 --> 00:33:50,090 But what we've seen today is that we've seen dynamic programming, basically 605 00:33:50,090 --> 00:33:53,380 bottom of computational, these [INAUDIBLE] relationship. 606 00:33:53,380 --> 00:33:56,980 It's one way of solving you know NP hard problems, okay? 607 00:33:56,980 --> 00:34:00,129 And when it works, it works very nicely, and it's typically, the not, if you think 608 00:34:00,129 --> 00:34:03,090 about these numbers and see if they are small, this is or even if n is large and 609 00:34:03,090 --> 00:34:07,665 K is reasonably small, this is going to be a fast algorithm. 610 00:34:07,665 --> 00:34:10,100 Okay? Well, this is, you know, this is the 611 00:34:10,100 --> 00:34:12,660 first class, this is first lecture of this class, okay? 612 00:34:12,660 --> 00:34:16,196 So next time we'll come back to the, to the knapsack problem, and look at branch 613 00:34:16,196 --> 00:34:18,150 and bound algorithm.