1 00:00:00,170 --> 00:00:07,550 So far, we have discussed the recursive approach for solving the zero one knapsack problem, and we 2 00:00:07,550 --> 00:00:14,360 have also seen that the solution that we came up with had an O of two to the power n time complexity, 3 00:00:14,360 --> 00:00:17,210 and an O of n space complexity. 4 00:00:17,240 --> 00:00:24,470 Let's now proceed with the memoization or top down approach for solving the knapsack problem, and we 5 00:00:24,470 --> 00:00:30,350 will see that by just adding a few lines of code, we will be able to convert the recursive approach 6 00:00:30,350 --> 00:00:32,480 to the memoization approach. 7 00:00:32,510 --> 00:00:36,650 So let's get started for discussing the memoization approach. 8 00:00:36,650 --> 00:00:38,510 Let me again take an example. 9 00:00:38,510 --> 00:00:47,030 Let's take the case where we are given three items and the capacity of the knapsack is eight units. 10 00:00:47,030 --> 00:00:52,940 We have previously seen that the recursion tree for this would look something like this. 11 00:00:52,940 --> 00:00:59,480 So let's say we are starting from the last index and we are going till the first index over here. 12 00:00:59,480 --> 00:01:03,590 So initially we are considering item three and we have two choices. 13 00:01:03,590 --> 00:01:08,330 We can either include item three or we can exclude item three. 14 00:01:08,330 --> 00:01:12,380 And then in this manner we proceed down the recursion tree. 15 00:01:12,470 --> 00:01:15,710 Now let's take a look at how we can memorize this. 16 00:01:15,950 --> 00:01:18,770 For this we will need a table. 17 00:01:18,770 --> 00:01:24,530 And the number of rows is going to be equal to the number of items that we have. 18 00:01:24,770 --> 00:01:30,890 And the number of columns is going to be equal to one plus the weight limit. 19 00:01:30,890 --> 00:01:33,680 So over here the weight limit was eight. 20 00:01:33,680 --> 00:01:36,800 So we are going to go from zero up to eight. 21 00:01:36,800 --> 00:01:41,120 So we have the weights over here and the items over here. 22 00:01:41,120 --> 00:01:44,930 And this is the dynamic programming table that we will be using. 23 00:01:44,930 --> 00:01:47,750 We can also call it the memoization table. 24 00:01:47,750 --> 00:01:52,430 Now initially we will fill all the cells with the value minus one. 25 00:01:52,430 --> 00:01:56,810 Now it's important to understand what a cell represents. 26 00:01:56,810 --> 00:01:58,970 So let's take this cell over here. 27 00:01:59,000 --> 00:02:07,160 Now this represents the subproblem where the remaining weight that can be added to the knapsack is equal 28 00:02:07,160 --> 00:02:10,040 to this weight over here, which is four. 29 00:02:10,040 --> 00:02:16,820 And the items that are available are these items over here which is i2 and i1. 30 00:02:16,820 --> 00:02:18,680 So that's this subproblem over here. 31 00:02:18,980 --> 00:02:21,680 Now what would be this subproblem over here. 32 00:02:21,740 --> 00:02:26,780 This subproblem would indicate that the remaining weight that can be added is seven. 33 00:02:26,780 --> 00:02:34,340 And the items that can be considered are I3, I2 and i1 or the three items that we have. 34 00:02:34,340 --> 00:02:41,060 And again finally this cell over here would indicate the remaining weight that can be added to the knapsack 35 00:02:41,060 --> 00:02:42,470 is equal to eight. 36 00:02:42,470 --> 00:02:46,760 And the items that we have are I3, I2 and i1. 37 00:02:46,760 --> 00:02:52,460 And whatever we will be filling in this cell would actually give us the answer, because you can see 38 00:02:52,460 --> 00:02:55,910 that this is the original problem which was asked of us. 39 00:02:55,910 --> 00:03:03,200 Now let's just quickly walk through the recursion tree and let's see how values will be filled in the 40 00:03:03,200 --> 00:03:05,150 dynamic programming table over here. 41 00:03:05,150 --> 00:03:09,050 So in this approach we are going from i3 to I1. 42 00:03:09,050 --> 00:03:15,800 So initially we are over here we have two choices whether to include i3 or exclude i3. 43 00:03:15,830 --> 00:03:21,380 Let's say we have written the code in such a manner that include happens before exclude. 44 00:03:21,380 --> 00:03:26,030 So the algorithm would go down this branch and it has included i3. 45 00:03:26,030 --> 00:03:32,360 And let's say it sees that item two also can be included because the remaining weight that can be included 46 00:03:32,360 --> 00:03:33,050 is three. 47 00:03:33,050 --> 00:03:35,720 And the weight of item two is just two. 48 00:03:35,750 --> 00:03:37,820 So the algorithm goes over here. 49 00:03:37,820 --> 00:03:40,070 And then we are considering item one. 50 00:03:40,070 --> 00:03:42,350 And item one has a weight of eight. 51 00:03:42,350 --> 00:03:45,110 And the remaining weight that can be included is one. 52 00:03:45,110 --> 00:03:47,480 So we don't have an include branch. 53 00:03:47,480 --> 00:03:49,610 So we set this to zero okay. 54 00:03:49,610 --> 00:03:53,270 And in over here we have the exclude branch. 55 00:03:53,270 --> 00:03:58,490 And when we come to the exclude branch the remaining weight that can be added is still one. 56 00:03:58,490 --> 00:04:00,350 But then we are not adding anything. 57 00:04:00,350 --> 00:04:02,930 So the value over here is zero as well. 58 00:04:02,930 --> 00:04:06,350 So we have the value zero over here and the value zero over here. 59 00:04:06,350 --> 00:04:10,250 So the maximum of these two values is zero itself. 60 00:04:10,250 --> 00:04:14,990 So this problem over here which is you have just item one. 61 00:04:14,990 --> 00:04:17,900 And the remaining weight to be filled is one. 62 00:04:17,900 --> 00:04:21,860 So this subproblem is going to have a value zero. 63 00:04:21,860 --> 00:04:25,910 And in the memoization approach we are going to store this. 64 00:04:25,910 --> 00:04:29,750 So the items that can be considered are just item one. 65 00:04:29,750 --> 00:04:32,090 So that's this row over here. 66 00:04:32,090 --> 00:04:36,290 And the remaining weight that can be added is equal to one. 67 00:04:36,290 --> 00:04:38,060 So that's this column over here. 68 00:04:38,060 --> 00:04:42,470 So we will be filling this cell over here with the value zero. 69 00:04:42,470 --> 00:04:43,460 So let's do that. 70 00:04:44,200 --> 00:04:52,240 So next time, let's say if we do encounter this sub problem, then we would not be computing it, but 71 00:04:52,240 --> 00:04:55,660 we would just retrieve what we have stored and we would return it. 72 00:04:55,690 --> 00:04:56,830 Now let's proceed. 73 00:04:56,830 --> 00:04:59,440 So the algorithm has found this answer. 74 00:04:59,440 --> 00:05:01,750 Then it comes down this branch. 75 00:05:01,750 --> 00:05:05,470 So over here we are just left with item one and weight three. 76 00:05:05,470 --> 00:05:09,370 We can't include it because item one has a weight of eight. 77 00:05:09,370 --> 00:05:11,560 So this over here becomes zero. 78 00:05:11,560 --> 00:05:14,590 And then if you exclude it the value is still zero. 79 00:05:14,590 --> 00:05:17,320 And the remaining weight that can be added is three. 80 00:05:17,320 --> 00:05:19,870 So you have zero over here and zero over here. 81 00:05:19,870 --> 00:05:24,670 So this subproblem over here also becomes zero right. 82 00:05:24,670 --> 00:05:27,340 So you come over here and this is also zero. 83 00:05:27,370 --> 00:05:30,040 The maximum between 0 and 0 is zero itself. 84 00:05:30,040 --> 00:05:35,770 So the subproblem where you can only consider item one and the remaining weight is three. 85 00:05:35,770 --> 00:05:39,130 So this subproblem over here becomes also zero. 86 00:05:39,130 --> 00:05:42,280 And we can store it in the memoization table. 87 00:05:42,280 --> 00:05:44,260 So we can only consider item one. 88 00:05:44,260 --> 00:05:45,910 And the remaining weight is three. 89 00:05:45,910 --> 00:05:47,800 So we store zero over here. 90 00:05:48,160 --> 00:05:50,080 Again this is also zero. 91 00:05:50,080 --> 00:05:51,100 This is also zero. 92 00:05:51,670 --> 00:05:54,340 And over here we have to add value two to this. 93 00:05:54,340 --> 00:05:55,960 So value two is three. 94 00:05:55,960 --> 00:05:58,180 So three plus zero becomes three. 95 00:05:58,180 --> 00:06:00,610 So this over here has returned three. 96 00:06:00,610 --> 00:06:02,650 And this would be returning zero. 97 00:06:02,650 --> 00:06:05,740 So the maximum between 3 and 0 is three. 98 00:06:05,740 --> 00:06:13,030 So that's why this subproblem over here where you have item two and one and the remaining weight to 99 00:06:13,030 --> 00:06:14,140 be added is three. 100 00:06:14,140 --> 00:06:17,680 So that's this cell over here becomes equal to three. 101 00:06:17,680 --> 00:06:20,560 And we fill it in the memoization table. 102 00:06:21,220 --> 00:06:22,210 Let's proceed. 103 00:06:22,210 --> 00:06:28,750 So this branch over here returns the value three plus value three value three is nine. 104 00:06:28,750 --> 00:06:30,310 So three plus nine is 12. 105 00:06:30,310 --> 00:06:31,750 So this returns 12. 106 00:06:31,750 --> 00:06:34,390 And then the algorithm comes down this path. 107 00:06:34,510 --> 00:06:35,170 All right. 108 00:06:35,170 --> 00:06:36,670 So we come over here. 109 00:06:37,260 --> 00:06:40,290 Then we would come over here and then we would come over here. 110 00:06:40,920 --> 00:06:43,500 And over here we are not able to include. 111 00:06:43,500 --> 00:06:44,610 So the value is zero. 112 00:06:44,610 --> 00:06:47,250 And when we exclude again we get the value zero. 113 00:06:47,280 --> 00:06:49,800 The maximum between 0 and 0 is zero itself. 114 00:06:49,800 --> 00:06:55,890 So this subproblem over here where you only have item one and the remaining weight to be added is six. 115 00:06:55,890 --> 00:07:00,120 So that's this cell over here that also becomes zero. 116 00:07:00,120 --> 00:07:01,530 So we add that over here. 117 00:07:02,190 --> 00:07:04,620 And then we return over here. 118 00:07:04,620 --> 00:07:05,820 Value two plus zero. 119 00:07:05,820 --> 00:07:06,990 Value two is three. 120 00:07:06,990 --> 00:07:09,870 So three plus zero three is getting returned over here. 121 00:07:10,200 --> 00:07:17,430 Then we come down over here and then we come over here where we are able to include item one, because 122 00:07:17,430 --> 00:07:22,500 you can see that the remaining weight to be added is eight and the weight of item one is eight itself. 123 00:07:22,500 --> 00:07:24,840 So we are able to include this. 124 00:07:24,840 --> 00:07:28,470 So when we do include it we get the value two back over here. 125 00:07:29,380 --> 00:07:30,700 And over here. 126 00:07:30,700 --> 00:07:33,190 When we exclude, we get back the value zero. 127 00:07:33,190 --> 00:07:36,070 So the maximum between 2 and 0 is two. 128 00:07:36,100 --> 00:07:42,550 So the value of this subproblem over here where you just have item one and the remaining weight to be 129 00:07:42,550 --> 00:07:44,110 added is equal to eight. 130 00:07:44,110 --> 00:07:47,110 So this subproblem over here becomes two. 131 00:07:47,140 --> 00:07:49,270 So we can store two over here. 132 00:07:49,270 --> 00:07:50,500 So let's do that. 133 00:07:52,230 --> 00:07:55,950 All right, so we get three over here and over here. 134 00:07:55,950 --> 00:07:57,600 This part over here returns two. 135 00:07:57,600 --> 00:08:02,430 So the maximum between 3 and 2 is going to be equal to three. 136 00:08:02,430 --> 00:08:07,320 So this subproblem over here where you have item two and item one. 137 00:08:07,320 --> 00:08:08,790 So that's this row over here. 138 00:08:08,790 --> 00:08:11,430 And the remaining weight to be added is eight. 139 00:08:11,430 --> 00:08:13,140 So that's this column. 140 00:08:13,140 --> 00:08:16,140 So this cell over here is going to take the value three. 141 00:08:16,140 --> 00:08:17,730 So we store that over here. 142 00:08:18,680 --> 00:08:20,540 And this returns three. 143 00:08:20,540 --> 00:08:23,720 And then the maximum between 3 and 12 is 12. 144 00:08:23,720 --> 00:08:28,310 So the problem where we have all the three items, that's this row. 145 00:08:28,310 --> 00:08:30,680 And the remaining wait to be added is eight. 146 00:08:30,680 --> 00:08:36,350 That's this column will have the value 12 because 12 is the maximum between 12 and 3. 147 00:08:36,350 --> 00:08:38,330 And we store that over here. 148 00:08:38,690 --> 00:08:39,800 So let's do that. 149 00:08:39,920 --> 00:08:43,820 And this is the answer to the problem at hand. 150 00:08:43,820 --> 00:08:49,640 So this is the memoization approach for solving the zero one knapsack problem.