1
00:00:00,110 --> 00:00:04,820
Let's now get into the code for solving the unbounded knapsack problem.

2
00:00:04,820 --> 00:00:08,270
And we are going to directly get into the tabulation approach.

3
00:00:08,270 --> 00:00:08,720
Okay.

4
00:00:08,720 --> 00:00:09,980
Now again over here.

5
00:00:09,980 --> 00:00:15,020
This is just going to be a tiny difference between the approach that we have taken to solve the zero

6
00:00:15,020 --> 00:00:16,040
one knapsack problem.

7
00:00:16,040 --> 00:00:19,520
So initially let's create a DP array okay.

8
00:00:19,520 --> 00:00:25,040
Which will have n plus one rows and w plus one columns.

9
00:00:26,000 --> 00:00:27,740
So let's go ahead and do that.

10
00:00:30,560 --> 00:00:38,390
Linked is n plus one, and the number of columns that we need is W plus one.

11
00:00:39,420 --> 00:00:44,790
And we are going to fill every cell in this 2d dp array with the value zero initially.

12
00:00:45,030 --> 00:00:45,570
Okay.

13
00:00:45,570 --> 00:00:50,340
And now we are going to iterate through the cells in the DP array.

14
00:00:50,340 --> 00:00:55,770
And we are going to leave out the first row and first column because we just need the values zero over

15
00:00:55,770 --> 00:00:56,100
there.

16
00:00:56,100 --> 00:00:58,590
And we already have taken care of that over here.

17
00:00:58,620 --> 00:00:59,100
Okay.

18
00:00:59,100 --> 00:01:03,090
And this is pretty similar to what we did in the zero one knapsack problem.

19
00:01:03,090 --> 00:01:13,860
So again let's have a nested for loop over here for let I equal to one I less than equal to n okay.

20
00:01:14,610 --> 00:01:18,570
And j is going to take the values from one up to w.

21
00:01:22,550 --> 00:01:31,370
Okay, now for each combination of I and J, we have to calculate the exclude value and the include

22
00:01:31,370 --> 00:01:31,880
value.

23
00:01:31,880 --> 00:01:41,000
So exclude is going to equal depee at I minus one j because we are excluding the item and in the ith

24
00:01:41,000 --> 00:01:41,900
row over here.

25
00:01:41,900 --> 00:01:46,100
And when it comes to include initially we will set it to zero.

26
00:01:46,100 --> 00:01:50,690
And we have discussed why this is required when we discussed the zero one knapsack problem.

27
00:01:50,690 --> 00:01:58,160
And ultimately we are going to say depee at I j is the maximum between exclude and include.

28
00:01:58,580 --> 00:02:01,550
Okay, so there's no change over here.

29
00:02:01,550 --> 00:02:09,500
Now the only change is going to be the fact that over here we can include an item multiple times.

30
00:02:09,500 --> 00:02:11,930
So over here again let's have the criteria.

31
00:02:11,930 --> 00:02:17,300
Let's have the check over here to determine whether this particular item can be included or not.

32
00:02:17,300 --> 00:02:26,510
So if weight at I minus one is less than or equal to j, then this item can be included and include

33
00:02:26,510 --> 00:02:36,950
would be equal to value at I minus one plus d p at I and j minus weight at I minus one.

34
00:02:37,280 --> 00:02:42,260
Now over here we see the difference when we solve these zero one knapsack problem.

35
00:02:42,260 --> 00:02:48,800
Over here we had DP at I minus one because an item could be included only one time, but because in

36
00:02:48,800 --> 00:02:52,160
this case an item can be included multiple times.

37
00:02:52,160 --> 00:02:58,880
Even though we included the item in the ith row, we don't need to shift to the I minus one row, but

38
00:02:58,880 --> 00:03:01,010
rather we stay over here itself.

39
00:03:01,010 --> 00:03:04,400
That is, we have DP at I itself over here and that's it.

40
00:03:04,400 --> 00:03:06,470
So this should help us solve this question.

41
00:03:06,470 --> 00:03:10,190
Now at the end we need to return the p n w.

42
00:03:10,190 --> 00:03:11,930
So let's go ahead and do that over here.

43
00:03:14,630 --> 00:03:15,740
And that's it.

44
00:03:15,770 --> 00:03:19,760
Now let's go ahead and run this code and see if it's passing all the test cases.

45
00:03:21,020 --> 00:03:21,440
Okay.

46
00:03:21,440 --> 00:03:22,220
So there's an error.

47
00:03:22,220 --> 00:03:25,910
I think I've made a typo so it should be excluded.

48
00:03:25,940 --> 00:03:29,630
I think I've missed the C so yeah it's exclude here right.

49
00:03:29,630 --> 00:03:32,510
So let's correct that and let's again run this code.

50
00:03:33,620 --> 00:03:34,100
All right.

51
00:03:34,100 --> 00:03:35,720
So there's one more error.

52
00:03:36,470 --> 00:03:40,220
So over here instead of J I've written I okay.

53
00:03:40,790 --> 00:03:41,750
Sorry for that.

54
00:03:41,750 --> 00:03:44,450
Now let's again run this code and see if it's working.

55
00:03:45,500 --> 00:03:48,260
And you can see that it's passing all the test cases.