1
00:00:00,280 --> 00:00:07,540
The unbounded knapsack question is very similar to the zero one knapsack problem which we have previously

2
00:00:07,540 --> 00:00:08,230
discussed.

3
00:00:08,230 --> 00:00:15,730
The only difference is that any item can be taken any number of times, or in other words, repetition

4
00:00:15,730 --> 00:00:20,200
with respect to taking the same item again and again is allowed.

5
00:00:20,200 --> 00:00:26,200
Okay, so that's the only difference when we compare this question with the zero one knapsack problem.

6
00:00:26,200 --> 00:00:32,320
We have already discussed the zero one knapsack problem in detail, where we first wrote the recursive

7
00:00:32,320 --> 00:00:34,630
solution and then we memoized it.

8
00:00:34,630 --> 00:00:40,330
And finally we discussed the tabulation approach as well as the space optimized tabulation approach.

9
00:00:40,330 --> 00:00:46,810
So over here let's directly start with the tabulation approach because we are already familiar with

10
00:00:46,810 --> 00:00:47,830
this question type.

11
00:00:47,830 --> 00:00:51,820
So let's get started now to discuss how we can solve this question.

12
00:00:51,820 --> 00:00:56,320
Let's take an example where let's say we are given three items.

13
00:00:56,320 --> 00:01:00,670
So the values of the items are two, four and nine.

14
00:01:00,670 --> 00:01:04,570
And their respective weights are eight, two and five.

15
00:01:04,570 --> 00:01:09,160
And the capacity of the knapsack over here is given as eight units.

16
00:01:09,160 --> 00:01:13,780
And again n is three, because we have three items in these two arrays.

17
00:01:13,780 --> 00:01:21,880
Now to solve this we will need a 2d dp array which has w plus one columns and n plus one rows.

18
00:01:21,880 --> 00:01:27,490
So this is the same approach that we have discussed in the zero one knapsack problem when we were discussing

19
00:01:27,490 --> 00:01:28,690
the tabulation approach.

20
00:01:28,690 --> 00:01:32,290
So we will have a similar DP table over here as well.

21
00:01:32,290 --> 00:01:36,580
And notice that because w is eight we have nine columns.

22
00:01:36,580 --> 00:01:42,040
And because n is equal to three we have four rows in this DP table.

23
00:01:42,040 --> 00:01:49,540
Now before we go ahead and fill this DP table, let's quickly review what a particular cell means okay.

24
00:01:49,540 --> 00:01:53,110
So for example what does this cell over here represent.

25
00:01:53,110 --> 00:02:00,460
This cell over here will represent the maximum profit or the maximum value that we can get in a knapsack

26
00:02:00,460 --> 00:02:02,830
where its capacity is four.

27
00:02:02,830 --> 00:02:06,190
So this value gives the capacity of the knapsack.

28
00:02:06,190 --> 00:02:10,870
And we can only take these two items okay.

29
00:02:10,870 --> 00:02:18,370
Similarly this cell over here would represent the maximum value that we can have in the knapsack where

30
00:02:18,370 --> 00:02:21,280
the weight limit of the knapsack is six.

31
00:02:21,280 --> 00:02:24,550
And we can only take this particular item over here.

32
00:02:24,550 --> 00:02:30,850
Now with this understanding let's try to fill the initial conditions in this DP table.

33
00:02:30,850 --> 00:02:35,110
Now what would be the values in the first row over here.

34
00:02:35,110 --> 00:02:43,060
Now from what we have over here, we can understand that the first row represents the scenario where

35
00:02:43,060 --> 00:02:44,620
we have no item.

36
00:02:44,620 --> 00:02:50,680
And if we have no item, then we cannot have any value in the knapsack.

37
00:02:50,680 --> 00:02:56,320
And for that reason, we can fill all the cells in the first row with zero.

38
00:02:56,320 --> 00:03:02,500
Similarly, when it comes to the first column, we can fill all these values with zero, because.

39
00:03:02,500 --> 00:03:09,490
Notice for the first column, the weight limit of the knapsack is zero, and if the weight limit or

40
00:03:09,490 --> 00:03:15,670
the capacity of the knapsack is zero, it means that we cannot add any item to the knapsack, and therefore

41
00:03:15,670 --> 00:03:17,740
the value in the knapsack would be zero.

42
00:03:17,740 --> 00:03:21,430
So these are the initial conditions for the DP table.

43
00:03:21,430 --> 00:03:27,910
Now we would have to go through each of these cells and fill their respective values.

44
00:03:27,910 --> 00:03:34,900
Now to do that for each cell we would have to calculate an include value and an exclude value.

45
00:03:34,900 --> 00:03:40,960
And then the maximum between include and exclude will be the value that we will store in that particular

46
00:03:40,960 --> 00:03:41,320
cell.

47
00:03:41,320 --> 00:03:44,950
So this is the same thing that we did for the zero one knapsack problem as well.

48
00:03:44,950 --> 00:03:49,540
So let's see how we can identify the value for dp at ij.

49
00:03:49,540 --> 00:03:52,300
So I'm just writing the general solution over here.

50
00:03:52,300 --> 00:03:57,520
Now to calculate exclude we just need to subtract I by one.

51
00:03:57,520 --> 00:04:01,720
So exclude will equal dp at I minus one j.

52
00:04:01,720 --> 00:04:09,130
Notice I j is still j itself because just by excluding there is no change in the weight, capacity or

53
00:04:09,130 --> 00:04:13,900
the remaining weight that can be added to the knapsack, but we are just excluding an item.

54
00:04:13,900 --> 00:04:17,080
So that's why I change this to I minus one.

55
00:04:17,080 --> 00:04:19,240
Now what about the include value?

56
00:04:19,240 --> 00:04:26,170
Now to calculate the include value, we will first have to check whether the item at hand can be included

57
00:04:26,170 --> 00:04:26,860
or not.

58
00:04:26,860 --> 00:04:27,310
Okay.

59
00:04:27,310 --> 00:04:35,140
And for that we'll have to check whether weight at I minus one is less than or equal to the value at

60
00:04:35,140 --> 00:04:35,590
J.

61
00:04:35,620 --> 00:04:36,010
Okay.

62
00:04:36,010 --> 00:04:41,950
Remember all these values represent j or for a particular cell you just need to see what's over here

63
00:04:41,950 --> 00:04:43,210
to get the value for J.

64
00:04:43,210 --> 00:04:47,860
And that represents the remaining capacity that can be added to the knapsack.

65
00:04:47,860 --> 00:04:55,000
And we can add an item to the knapsack only if its weight is less than or equal to the remaining capacity

66
00:04:55,000 --> 00:04:57,010
that can be added to the knapsack.

67
00:04:57,010 --> 00:04:59,890
Now over here, when we are considering the item.

68
00:05:00,010 --> 00:05:05,650
Term at index I in the deep table over here, or the item at the I th row.

69
00:05:06,580 --> 00:05:07,060
Okay.

70
00:05:07,060 --> 00:05:12,880
We have to do I minus one because the wait array is zero indexed.

71
00:05:12,880 --> 00:05:19,510
For example notice over here item two is at the row with index two okay.

72
00:05:19,510 --> 00:05:25,570
And item two in the values array or in the wait array is at index one.

73
00:05:25,570 --> 00:05:25,960
Okay.

74
00:05:25,960 --> 00:05:29,860
So we have to change this two over here to this one.

75
00:05:29,860 --> 00:05:32,980
And that's why we have to do wait at I minus one.

76
00:05:32,980 --> 00:05:39,640
Now let's assume that we found that wait at I minus one is indeed less than or equal to J.

77
00:05:39,640 --> 00:05:44,200
And therefore we can go ahead and include that particular item to the knapsack.

78
00:05:44,200 --> 00:05:51,820
Now when we include that particular item to the knapsack, the value of items in the knapsack will increase

79
00:05:51,820 --> 00:05:55,720
by val at I minus one, and to that.

80
00:05:57,220 --> 00:06:02,530
We'll have to add DP and I and then j minus weight at I minus one.

81
00:06:02,560 --> 00:06:04,360
Now let's try to understand this.

82
00:06:04,360 --> 00:06:10,840
So over here notice I have again I minus one over here as well as over here okay.

83
00:06:10,840 --> 00:06:14,170
And that's for zero indexing as we have discussed okay.

84
00:06:14,170 --> 00:06:17,500
So we have to change this two for example to one.

85
00:06:17,500 --> 00:06:21,490
So that's why over here and over here we have to do I minus one.

86
00:06:21,490 --> 00:06:29,650
So again the rule of thumb over here is that for changing the item at index I in the DP table is at

87
00:06:29,650 --> 00:06:33,010
index I minus one in the value and weight array.

88
00:06:33,010 --> 00:06:33,550
Okay.

89
00:06:33,550 --> 00:06:37,330
So that explains why we have I minus one over here and over here.

90
00:06:37,330 --> 00:06:42,220
And again we have seen why we have valid I minus one over here because we have added this item to the

91
00:06:42,220 --> 00:06:42,790
knapsack.

92
00:06:42,790 --> 00:06:48,100
And therefore the value of items in the knapsack would increase by this amount over here.

93
00:06:48,100 --> 00:06:54,340
And because we have added this item, the remaining capacity or the remaining weight that can be added

94
00:06:54,340 --> 00:07:00,880
to the knapsack has to decrease and for getting the remaining amount or the remaining capacity that

95
00:07:00,880 --> 00:07:05,980
can be added to the knapsack, we have to do j minus weight at I minus one.

96
00:07:05,980 --> 00:07:13,240
And over here notice we still have DP at I, even though we included an item to the knapsack.

97
00:07:13,240 --> 00:07:20,020
And that's because in the question, it's mentioned that an item can be added to the knapsack an unlimited

98
00:07:20,020 --> 00:07:20,830
number of times.

99
00:07:20,830 --> 00:07:25,960
So this is where this question over here differs from the zero one knapsack question.

100
00:07:25,960 --> 00:07:28,210
And again the difference was there.

101
00:07:28,210 --> 00:07:30,130
You could add an item only once.

102
00:07:30,130 --> 00:07:35,080
But over here you can add an item an unlimited number of times okay.

103
00:07:35,080 --> 00:07:40,420
So we have seen that include is valid I minus one plus DP at I.

104
00:07:40,420 --> 00:07:43,360
And then you have j minus weight at I minus one.

105
00:07:43,360 --> 00:07:49,300
And we have seen that this over here gives the remaining capacity that can be added to the knapsack.

106
00:07:49,300 --> 00:07:56,590
So at this point we have calculated exclude and include and then we would have to find the maximum between

107
00:07:56,590 --> 00:07:57,250
these two.

108
00:07:57,250 --> 00:08:00,610
And that value would be filled at dp at I j.

109
00:08:00,760 --> 00:08:04,570
Now we're going to do this for all of these remaining cells.

110
00:08:04,570 --> 00:08:11,500
And once we have filled all of these up we will get the answer at this particular cell over here which

111
00:08:11,500 --> 00:08:13,870
is DP at n w.

112
00:08:13,870 --> 00:08:15,070
And again why is that.

113
00:08:15,070 --> 00:08:21,970
So it is the case because this cell over here represents the maximum profit that can be added to the

114
00:08:21,970 --> 00:08:25,540
knapsack where the capacity of the knapsack is eight.

115
00:08:25,540 --> 00:08:28,960
And we can consider all these three items.

116
00:08:28,960 --> 00:08:33,460
And notice that that in fact is what the question asks us to find.

117
00:08:33,460 --> 00:08:36,400
So that's why we will get the answer over here.

118
00:08:36,400 --> 00:08:38,410
And we'll just have to return that.

119
00:08:38,410 --> 00:08:41,500
So this is the approach that we will take to solve this question.

120
00:08:41,500 --> 00:08:47,380
In the next video, let's try to think of the space and time complexity of the approach that we came

121
00:08:47,380 --> 00:08:48,490
up with over here.