1 00:00:02,700 --> 00:00:05,380 We've now got two dynamic programming algorithms under our belt. 2 00:00:05,380 --> 00:00:08,140 We know how to compute weighted independence sets in path graphs. 3 00:00:08,140 --> 00:00:11,370 We also know a dynamic programming solution to the famous knapsack problem. 4 00:00:11,370 --> 00:00:14,480 But before I proceed to still more useful and 5 00:00:14,480 --> 00:00:17,770 famous dynamic programming algorithms Let's pause for a sanity check. 6 00:00:17,770 --> 00:00:19,520 Let's go through a worked example 7 00:00:19,520 --> 00:00:22,150 for that, dynamic programming algorithm for Knapsack. 8 00:00:22,150 --> 00:00:24,920 Just to make sure that everything is crystal clear. 9 00:00:26,140 --> 00:00:27,780 So, for reference, let me just, 10 00:00:27,780 --> 00:00:29,820 rewrite the key point to the Knapsack algorithm. 11 00:00:29,820 --> 00:00:32,370 So first, we have a 2D, 2D array A. 12 00:00:32,370 --> 00:00:35,030 And for initialization, just whenever I equals 0. 13 00:00:35,030 --> 00:00:35,262 That is, you. 14 00:00:35,262 --> 00:00:36,580 You can't use any items at all. 15 00:00:36,580 --> 00:00:39,840 Of course the optimal solution value is 0, and then I'm just going 16 00:00:39,840 --> 00:00:43,300 to rewrite the same occurrence that we had in the previous couple of videos. 17 00:00:43,300 --> 00:00:43,800 So 18 00:00:50,210 --> 00:00:54,120 you'll recall that in the main loop, when you're considering a given item a, 19 00:00:54,120 --> 00:00:59,570 and a residual cap-, nap sack capacity x, you take the better of two solutions. 20 00:00:59,570 --> 00:01:02,650 Either you inherit the solution With i minus one and 21 00:01:02,650 --> 00:01:06,050 the residual capacity x that corresponds to not taking item 22 00:01:06,050 --> 00:01:08,250 i, or if you do take item i you get 23 00:01:08,250 --> 00:01:10,420 a credit of Visa Buy the value for that item. 24 00:01:10,420 --> 00:01:15,780 But the residual capacity drops from x to x minus the weight of item i and 25 00:01:15,780 --> 00:01:18,560 you look up the optimal solution for that smaller sub problem. 26 00:01:19,980 --> 00:01:23,840 So, for our concrete example, let's just look at a case with 4 items. 27 00:01:23,840 --> 00:01:27,670 An initial nap sack capacity capital W equal to 6, 28 00:01:27,670 --> 00:01:32,109 and the values and weights of the 4 items as follows. 29 00:01:33,570 --> 00:01:35,790 So, I'm going to describe the most straightforward 30 00:01:35,790 --> 00:01:38,680 implementation of the dynamic programming algorithm for knapsack. 31 00:01:38,680 --> 00:01:41,330 We're literally just going to explicitly form the 2D 32 00:01:41,330 --> 00:01:42,210 array A. 33 00:01:42,210 --> 00:01:46,680 One index for i will range between 0 and n, the other 34 00:01:46,680 --> 00:01:51,530 index for x will range between 0 and capital W, the original capacity. 35 00:01:51,530 --> 00:01:55,680 There certainly a lot of optimizations you can apply when filling in these tables. 36 00:01:55,680 --> 00:01:59,650 In fact, the future programming assignment will ask you to consider some. 37 00:01:59,650 --> 00:02:02,080 But just to make sure the basic algorithm is totally 38 00:02:02,080 --> 00:02:06,220 clear, let's just stick with that naive implementation for now. 39 00:02:06,220 --> 00:02:09,960 So we begin with the initialization and setting A0X 40 00:02:09,960 --> 00:02:11,830 to be equal to 0 for all x, just 41 00:02:11,830 --> 00:02:14,440 means we take the leftmost column corresponding to i 42 00:02:14,440 --> 00:02:17,710 equals 0 and we fill that in entirely with 0's. 43 00:02:17,710 --> 00:02:19,560 Now in a real implementation there's no reason 44 00:02:19,560 --> 00:02:21,460 to explicitly store these 0's, you know they are 45 00:02:21,460 --> 00:02:23,570 there, but again to keep the picture clear let's 46 00:02:23,570 --> 00:02:26,320 just fill in the 0's in the left column. 47 00:02:26,320 --> 00:02:28,460 Now we proceed to the main while loop and 48 00:02:28,460 --> 00:02:31,590 recall the outer for loop just increments the index i 49 00:02:31,590 --> 00:02:34,230 for the item that we're considering so the outer for loop 50 00:02:34,230 --> 00:02:38,500 is considering each of the columns in turn from left to right. 51 00:02:38,500 --> 00:02:41,790 Now for a fixed value of i for a fixed column, in the 52 00:02:41,790 --> 00:02:45,455 inner for loop we consider all values of x from 0 to capital W. 53 00:02:45,455 --> 00:02:47,530 So that just corresponds in a given column we're 54 00:02:47,530 --> 00:02:50,640 going to fill in the entries from bottom to top. 55 00:02:50,640 --> 00:02:53,510 So we begin this double for loop with the second 56 00:02:53,510 --> 00:02:57,810 column i equal 1 and at the bottom x equals 0. 57 00:02:57,810 --> 00:02:59,320 Now in general when we fill in one of these 58 00:02:59,320 --> 00:03:02,410 table entries, we're going to take the better of two solutions. 59 00:03:02,410 --> 00:03:07,090 Either we just inherit the solution from the column to the left in the same row. 60 00:03:07,090 --> 00:03:08,760 This corresponds to skipping item i. 61 00:03:08,760 --> 00:03:11,178 Or we add the value of the current item. 62 00:03:11,178 --> 00:03:13,360 to the opitimal solution that we extract from 63 00:03:13,360 --> 00:03:15,830 the column one to the left, but also W 64 00:03:15,830 --> 00:03:16,360 [UNKNOWN] 65 00:03:16,360 --> 00:03:17,260 rows down. 66 00:03:17,260 --> 00:03:20,860 So, that corresponds to reducing the residual capacity of W sub i. 67 00:03:20,860 --> 00:03:23,790 Now, for the early subproblems in a column, where 68 00:03:23,790 --> 00:03:27,020 you have essentially 0 residual capacity, it's kind of degenerate. 69 00:03:27,020 --> 00:03:29,060 Right so, if your residual capacity x is 70 00:03:29,060 --> 00:03:31,730 actually less than the weight of the current 71 00:03:31,730 --> 00:03:33,940 item you're considering, w sub i, you have 72 00:03:33,940 --> 00:03:36,620 no choice but to inherit the previous solution. 73 00:03:36,620 --> 00:03:39,540 You're actually not allowed to pack the current item i. 74 00:03:39,540 --> 00:03:41,300 So concretely in this example, 75 00:03:41,300 --> 00:03:45,680 in the first column, notice the weight of the first item is 4. 76 00:03:45,680 --> 00:03:49,510 So that means if x equals 0 or 1 or 2 or 3. 77 00:03:49,510 --> 00:03:51,300 We're actually not permitted to choose item 78 00:03:51,300 --> 00:03:53,159 one, we're going to run out of residual capacity. 79 00:03:53,159 --> 00:03:55,760 So in the first, bottommost four rows 80 00:03:55,760 --> 00:03:55,760 [INAUDIBLE], 81 00:03:55,760 --> 00:04:00,540 we're forced to inherit the solution from the column to the left. 82 00:04:00,540 --> 00:04:05,510 So it is the first four 0's from the left column get copied over to column with i 83 00:04:05,510 --> 00:04:10,840 equals 1. 84 00:04:10,840 --> 00:04:13,751 Now, in this outer iteration of the, in the first outer iteration of 85 00:04:13,751 --> 00:04:16,800 the for-loop, once x reaches 4, now 86 00:04:16,800 --> 00:04:18,470 there's actually an interesting decision to make. 87 00:04:18,470 --> 00:04:20,300 We have the option of inheriting the 0, 88 00:04:20,300 --> 00:04:21,800 immediately to the left. 89 00:04:21,800 --> 00:04:26,060 Or, we can take item 1, therefore getting a value of 3. 90 00:04:26,060 --> 00:04:28,672 And then we inherit the solution from a 0, 0. 91 00:04:28,672 --> 00:04:32,520 And now A000 has a 0, but were obviously happy to get this value of three. 92 00:04:32,520 --> 00:04:38,770 So that's going to determine the max we're going to except V sub i , plus a of 0, 0. 93 00:04:38,770 --> 00:04:42,550 And that gives us a three in this next table entry. 94 00:04:46,050 --> 00:04:47,620 By the same reasoning, we're going to fill in 95 00:04:47,620 --> 00:04:50,760 the uppermost rows of column one with these threes. 96 00:04:50,760 --> 00:04:53,170 We're, we certainly would prefer just taking the 97 00:04:53,170 --> 00:04:54,890 item one which we're now allowed to do. 98 00:04:54,890 --> 00:04:56,580 We have enough residual capacity. 99 00:04:56,580 --> 00:05:00,299 As opposed to just inheriting the 0 from the column one to the left. 100 00:05:03,840 --> 00:05:06,100 So that's how we fill in the column of i equal one. 101 00:05:06,100 --> 00:05:07,510 Moving on to i equal two. 102 00:05:07,510 --> 00:05:11,060 Again, so here notice that item two has a weight of three. 103 00:05:11,060 --> 00:05:15,360 So again, the bottommost three rows when x equals 0, or one, or two. 104 00:05:15,360 --> 00:05:16,480 There's nothing we can do. 105 00:05:16,480 --> 00:05:18,720 We don't have the option of picking item number two. 106 00:05:18,720 --> 00:05:20,440 We don't have enough digital capacity. 107 00:05:20,440 --> 00:05:23,900 So we just copy the values from column i equal 1 over. 108 00:05:23,900 --> 00:05:28,950 Those happen to be 0's, so that gives us three 0's to start column two. 109 00:05:31,490 --> 00:05:33,970 Now when i equals 2 and x equals 3, now 110 00:05:33,970 --> 00:05:37,510 we're, we have enough residual capacity to take item two. 111 00:05:37,510 --> 00:05:40,840 And we're certainly, much happier to take the value of 2. 112 00:05:40,840 --> 00:05:42,390 Which is the value of item number two, as 113 00:05:42,390 --> 00:05:45,140 opposed to inheriting the 0, 1 column on the left. 114 00:05:45,140 --> 00:05:48,220 So that gives us a two in the column i 115 00:05:48,220 --> 00:05:52,450 equals 2, with a residual capacity x equal to 3. 116 00:05:52,450 --> 00:05:56,560 So perhaps the first truly interesting table entry to fill in is when i 117 00:05:56,560 --> 00:05:59,850 equals 2 and x equals 4, because in this case, we 118 00:05:59,850 --> 00:06:02,940 actually have two different non trivial solutions we have to pick from. 119 00:06:02,940 --> 00:06:05,620 So one solution, as usual, we can just copy over the number, which 120 00:06:05,620 --> 00:06:08,720 is one column to the left, but actually in this case, there's a 3. 121 00:06:08,720 --> 00:06:11,759 There's no longer a 0 to the To the left there's a 3 to the left Right? 122 00:06:11,759 --> 00:06:14,180 A 1,4 is equal to 3. 123 00:06:14,180 --> 00:06:17,290 Our other option is to take the second item getting us a value 124 00:06:17,290 --> 00:06:21,720 of 2 and add that to whatever is in the leftmost column but shifted 125 00:06:21,720 --> 00:06:24,610 down by 3, because 3 is the weight of the second item. 126 00:06:24,610 --> 00:06:27,560 And you'll note that A of 1,1 is 0. 127 00:06:27,560 --> 00:06:30,910 So, picking the current item would just give us 2 plus 0 equals 0. 128 00:06:30,910 --> 00:06:34,500 We'd prefer to just inherit the 3, from the column one to the left. 129 00:06:34,500 --> 00:06:37,340 That is, we prefer to skip item two, so 130 00:06:37,340 --> 00:06:39,490 that we get the value from item one instead. 131 00:06:39,490 --> 00:06:43,179 The upper two rows of the second, the column with i 132 00:06:43,179 --> 00:06:46,190 equal 2 are filled in with 3s for exactly the same reason. 133 00:06:46,190 --> 00:06:46,890 So for example 134 00:06:46,890 --> 00:06:48,530 in the top row, what are our options? 135 00:06:48,530 --> 00:06:50,740 Well we can inherit the three that's one to the left. 136 00:06:50,740 --> 00:06:53,130 If we actually use item number two, that 137 00:06:53,130 --> 00:06:56,060 knocks a residual capacity down to three and 138 00:06:56,060 --> 00:07:00,410 then you have 1,3 equals 0, so again, you'd rather have the three than the two. 139 00:07:01,720 --> 00:07:04,450 Moving on to the penultimate column, 1i equals 3, for the 140 00:07:04,450 --> 00:07:08,430 usual reasons, we have to fill in the two bottommost rows. 141 00:07:08,430 --> 00:07:09,330 with a 0. 142 00:07:09,330 --> 00:07:12,050 Notice that the weight of the third item equals 2. 143 00:07:12,050 --> 00:07:16,670 So we need a residual capacity x equal to 2 before we can actually use it. 144 00:07:16,670 --> 00:07:20,220 Now, when x equals 2, we'd much rather have the value 145 00:07:20,220 --> 00:07:23,830 of 4 for the current item than to copy the 0 over. 146 00:07:23,830 --> 00:07:29,870 So we're going to fill in the entry A of 3,2 of 4, the value of the third item. 147 00:07:29,870 --> 00:07:33,110 Similar reasons apply when x equals three or four. 148 00:07:33,110 --> 00:07:37,240 So here the alternative starts looking better, right, so in the row where x 149 00:07:37,240 --> 00:07:40,510 equals three the value that we'd inherit would be two. 150 00:07:40,510 --> 00:07:43,320 In the row where x equals four, the value we'd inherit would be three. 151 00:07:43,320 --> 00:07:45,710 But in both of these cases we'd prefer to have the 152 00:07:45,710 --> 00:07:49,390 immediate gratification of the value of four from the third item. 153 00:07:49,390 --> 00:07:52,930 And just inherit the empty solution with the residual capacity. 154 00:07:52,930 --> 00:07:55,350 So when X equals 3 and X equals 4, we're just 155 00:07:55,350 --> 00:07:59,870 going to take the third item and get a value of 4. 156 00:07:59,870 --> 00:08:02,495 Now good things really start happening once X equals 157 00:08:02,495 --> 00:08:08,120 5, because at that point we can both grab the third item and gets it's value of 4. 158 00:08:08,120 --> 00:08:10,460 But now, we knocked down the residual capacity only 159 00:08:10,460 --> 00:08:14,130 to 5 minus 2 which equals 3, and when you 160 00:08:14,130 --> 00:08:16,490 have i equal 2, and x equal 3, you 161 00:08:16,490 --> 00:08:19,535 actually get to, a value of 2, in that case. 162 00:08:19,535 --> 00:08:22,750 So, we're going to fill in the entry for i equals 3 and 163 00:08:22,750 --> 00:08:27,410 x equal 5 with 4, the value of the current item, plus 2, 164 00:08:27,410 --> 00:08:29,825 the optimal solution to the corresponding sub-problem. 165 00:08:32,600 --> 00:08:34,340 It gets even better when x equals 6. 166 00:08:34,340 --> 00:08:37,020 We're again going to take the third item, get its value of 4. 167 00:08:37,020 --> 00:08:41,020 But now, in the smaller subproblem, when i equals 3 and x equals 4, we actually 168 00:08:41,020 --> 00:08:44,043 get a value of 3, so the value here's going to be 4 plus 3, or 7. 169 00:08:46,240 --> 00:08:50,920 Moving to the last column when i equals 4, so here the fourth item has weight 3, so 170 00:08:50,920 --> 00:08:54,620 that means when x equals 0, or 1, or 2, we don't even have the option of picking it. 171 00:08:54,620 --> 00:08:56,100 We have no choice but to copy over the 172 00:08:56,100 --> 00:08:58,730 number from the column to the left, so that's going to 173 00:08:58,730 --> 00:09:03,780 give us a 0, and a 0, and a 4, for the first three rows of the final column. 174 00:09:03,780 --> 00:09:08,080 So now in column 3, we do have the option of picking the fourth item. 175 00:09:08,080 --> 00:09:09,620 That'll give us a value of 4. 176 00:09:09,620 --> 00:09:11,270 You also have the option of just copying over 177 00:09:11,270 --> 00:09:13,610 the value in the column to the left. That will also give us a 4. 178 00:09:13,610 --> 00:09:14,460 So, we have a tie. 179 00:09:14,460 --> 00:09:16,158 And in some sense it doesn't matter. 180 00:09:16,158 --> 00:09:21,570 So we're going to fill in the entry of 4, when i equals 4, and x equals 3. 181 00:09:21,570 --> 00:09:24,860 The exact same reasoning applies when x equals 4. 182 00:09:24,860 --> 00:09:26,860 We're making the comparison between two thing, two 183 00:09:26,860 --> 00:09:28,823 things of equal value, both equal to 4. 184 00:09:28,823 --> 00:09:32,620 Now, when x equals 5, we let the good times roll. 185 00:09:32,620 --> 00:09:36,890 We both can take the fourth item, and we get a value of 4 for the the fourth item. 186 00:09:36,890 --> 00:09:40,390 But now, when we subtract out its weight, we get a residual capacity of 2, 187 00:09:40,390 --> 00:09:44,880 and when x equals 2 and i equals 3, we also get a value of 4. 188 00:09:44,880 --> 00:09:48,383 So in this entry, we can write 4 plus 4, or 8. 189 00:09:49,730 --> 00:09:51,970 And that's superior to the alternative, which is just 190 00:09:51,970 --> 00:09:54,730 inheriting the six from the column to the left. 191 00:09:54,730 --> 00:09:58,550 Same story holds when x equals to six we can take the fourth 192 00:09:58,550 --> 00:10:00,070 item, get the immediate gratification of 193 00:10:00,070 --> 00:10:02,740 four, get four from the smaller subproblem. 194 00:10:02,740 --> 00:10:05,930 When i equals 3 and x equals 3, and that eight beats 195 00:10:05,930 --> 00:10:10,920 out the alternative, inheriting the seven from the column to the left. 196 00:10:10,920 --> 00:10:13,170 So that completes the forward pass of the dynamic 197 00:10:13,170 --> 00:10:16,510 programming algorithm, filling in the table systematically using our recurrence. 198 00:10:16,510 --> 00:10:18,140 When it completes, of course, the optimal 199 00:10:18,140 --> 00:10:20,040 solution value is in the upper right corner. 200 00:10:20,040 --> 00:10:22,240 It's the value of the biggest sub-problem. 201 00:10:22,240 --> 00:10:25,060 So we know, at this point, that the max value 202 00:10:25,060 --> 00:10:28,547 of any feasible solution to this knapsack instance is 8. 203 00:10:28,547 --> 00:10:32,070 And as as we've discussed after you've filled in 204 00:10:32,070 --> 00:10:33,920 the table in the forward pass, if you want 205 00:10:33,920 --> 00:10:35,970 to get your grubby little hands on the optimal 206 00:10:35,970 --> 00:10:39,160 solution itself, you can do that with a reverse pass. 207 00:10:39,160 --> 00:10:41,910 There's a reconstruction post-processing step. 208 00:10:41,910 --> 00:10:42,680 How does that work? 209 00:10:42,680 --> 00:10:44,749 Well you start with the biggest subproblems, in this 210 00:10:44,749 --> 00:10:47,160 case when i equals 4 and x equals 6. 211 00:10:47,160 --> 00:10:50,040 And then you ask, by which branch of 212 00:10:50,040 --> 00:10:53,040 the recurrence did we fill in this table entry. 213 00:10:53,040 --> 00:10:53,570 And that gives 214 00:10:53,570 --> 00:10:56,780 us guidance over whether to pick this item or not. 215 00:10:56,780 --> 00:10:58,170 So, how did we get this 8? 216 00:10:58,170 --> 00:10:59,670 Did we inherit it from the column one 217 00:10:59,670 --> 00:11:02,650 to the left, corresponding to not taking item 4? 218 00:11:02,650 --> 00:11:05,090 Or, did we get it from the column to the left, in 219 00:11:05,090 --> 00:11:07,810 the sub-problem with decrease, with residual 220 00:11:07,810 --> 00:11:10,380 capacity decreased by the weight of item. 221 00:11:10,380 --> 00:11:13,250 Four. Corresponding to taking item four. 222 00:11:13,250 --> 00:11:15,920 Well, if you look at it, we didn't just inherit the solution 223 00:11:15,920 --> 00:11:19,300 in the column to the left which does indeed correspond to taking 224 00:11:19,300 --> 00:11:20,090 item four. 225 00:11:20,090 --> 00:11:23,200 That was the better of the two options we used to fill in this table entry. 226 00:11:23,200 --> 00:11:27,050 So, that means that in the optimal solution, item four will be there. 227 00:11:28,720 --> 00:11:30,450 So, having figured that out, we trace back through 228 00:11:30,450 --> 00:11:33,040 the table, we say, okay, well, let's look then 229 00:11:33,040 --> 00:11:35,090 at the table entry that we used to build 230 00:11:35,090 --> 00:11:37,150 up to this optimal solution to the big problem. 231 00:11:37,150 --> 00:11:40,380 So, that corresponds to going one column to the left, and a number of 232 00:11:40,380 --> 00:11:44,430 columns down equal to the weight of this fourth item, that is three rows down. 233 00:11:45,540 --> 00:11:47,170 Now we ask exactly the same question. 234 00:11:47,170 --> 00:11:49,220 Did we inherit the solution from the previous 235 00:11:49,220 --> 00:11:51,590 column, corresponding to picking this item, or did we 236 00:11:51,590 --> 00:11:54,900 use this item, and build from a solution 237 00:11:54,900 --> 00:11:57,310 to a smaller sit problem from the previous column. 238 00:11:57,310 --> 00:11:59,210 Well, again, you know, where did this 4 come from? 239 00:11:59,210 --> 00:12:00,930 It didn't come from immediately to the left. 240 00:12:00,930 --> 00:12:02,890 It came from the value of item 3 241 00:12:02,890 --> 00:12:06,210 plus the optimal solution with a decreased residual capacity. 242 00:12:06,210 --> 00:12:08,130 So that means that the optimal solution. 243 00:12:08,130 --> 00:12:10,760 Also includes item number three. 244 00:12:10,760 --> 00:12:11,520 So, what do we do then? 245 00:12:11,520 --> 00:12:15,800 We trace back, we go one column to the left, and we have to go now two rows down. 246 00:12:15,800 --> 00:12:18,940 Two rows because the weight of the third item is two. 247 00:12:21,050 --> 00:12:24,680 So, that leads us to A(2,1) and at this point, the 248 00:12:24,680 --> 00:12:28,070 residual capacity is so small that we have no choice but to 249 00:12:28,070 --> 00:12:30,730 inherit the numbers from the left, so we're not going to be able 250 00:12:30,730 --> 00:12:34,210 to pack either item one or item two into the optimal solution. 251 00:12:34,210 --> 00:12:38,160 So at this point, we just go left during our traceback, 252 00:12:38,160 --> 00:12:40,900 and then when we get to i equals 0, we're done. 253 00:12:40,900 --> 00:12:43,230 We know we've constructed the optimal solution, which in 254 00:12:43,230 --> 00:12:45,760 this case is item number 3 and item number 4. 255 00:12:45,760 --> 00:12:46,080 That's how 256 00:12:46,080 --> 00:12:50,100 you get an optimal value of 8 in this particular knapsack instance.