1
00:00:00,570 --> 00:00:01,620
Welcome back.

2
00:00:01,620 --> 00:00:08,610
Let's now do a famous coding interview question, which is called the zero one knapsack problem.

3
00:00:08,610 --> 00:00:10,350
Now let's read the question.

4
00:00:10,350 --> 00:00:16,710
You are provided with a set of n items, each with a specified weight and value.

5
00:00:16,770 --> 00:00:25,620
Your objective is to pack these items into a backpack with a weight limit of W, maximizing the total

6
00:00:25,620 --> 00:00:27,780
value of items in the backpack.

7
00:00:27,990 --> 00:00:34,890
Specifically, you have two arrays, so this is the value array representing the values of the items.

8
00:00:34,890 --> 00:00:38,430
And you have the weight array indicating their weights.

9
00:00:38,430 --> 00:00:41,670
So these are the indices from zero to n minus one.

10
00:00:41,670 --> 00:00:46,710
Additionally you have a weight limit w for the backpack.

11
00:00:47,160 --> 00:00:54,720
The challenge is to determine the most valuable combination of items where the total weight does not

12
00:00:54,720 --> 00:00:56,040
exceed w.

13
00:00:56,370 --> 00:01:05,880
Note that each item is unique and indivisible, meaning it must be either taken as a whole or left entirely.

14
00:01:05,880 --> 00:01:07,260
So this is the question.

15
00:01:07,260 --> 00:01:11,880
Now this is a variation of a problem called zero one knapsack problem.

16
00:01:11,880 --> 00:01:17,940
Now, when it comes to knapsack problems, there are typically three common variations.

17
00:01:17,940 --> 00:01:21,210
So the first one is the zero one knapsack over here.

18
00:01:21,210 --> 00:01:26,880
And again a knapsack is just a backpack or a bag.

19
00:01:26,880 --> 00:01:34,860
Now over here this is the zero one knapsack problem, because it's given that the items are unique and

20
00:01:34,860 --> 00:01:35,640
indivisible.

21
00:01:35,640 --> 00:01:40,710
So unique means you just have one item of a certain value and weight.

22
00:01:40,710 --> 00:01:48,150
Now, if you could pack item one a multiple number of times into the bag, that would be a variation

23
00:01:48,150 --> 00:01:52,410
of the knapsack problem called the unbounded knapsack.

24
00:01:52,410 --> 00:01:52,830
Okay.

25
00:01:52,830 --> 00:01:55,590
But over here it says the items are unique.

26
00:01:55,590 --> 00:01:58,560
So you just have one set of each item.

27
00:01:58,560 --> 00:02:03,180
And over here it's also mentioned that the items are indivisible.

28
00:02:03,180 --> 00:02:07,920
So that means that you can't have half of an item added to the backpack.

29
00:02:07,920 --> 00:02:15,510
So if the items were not indivisible, it would be another variation of the knapsack problem called

30
00:02:15,510 --> 00:02:18,150
the fractional knapsack problem.

31
00:02:18,150 --> 00:02:24,540
Now the fractional knapsack problem is not a dynamic programming problem.

32
00:02:24,540 --> 00:02:28,950
This is something that's typically solved with the greedy approach.

33
00:02:28,950 --> 00:02:33,480
So we have discussed the three common variations of the knapsack problem.

34
00:02:33,480 --> 00:02:36,990
Over here we are dealing with the zero one knapsack problem.

35
00:02:36,990 --> 00:02:42,840
Zero one indicates that you can either include an item which is the one over here, or you can exclude

36
00:02:42,840 --> 00:02:46,350
an item from the bag, which is what the zero over here indicates.

37
00:02:46,350 --> 00:02:50,940
And the items are indivisible and the items are unique.

38
00:02:50,940 --> 00:02:57,510
Now, if the items were not unique, that's the variation of the knapsack problem called unbounded knapsack.

39
00:02:57,510 --> 00:02:59,400
We will soon discuss that.

40
00:02:59,400 --> 00:03:06,180
And then if the items were not indivisible, that's the variation of the knapsack problem called fractional

41
00:03:06,180 --> 00:03:06,780
knapsack.

42
00:03:06,780 --> 00:03:10,680
And we've discussed that this is solved using the greedy algorithmic approach.

43
00:03:10,680 --> 00:03:14,490
Now let's get started with the zero one knapsack problem.

44
00:03:14,490 --> 00:03:18,660
Now to understand this problem in a better manner, let's take an example.

45
00:03:18,660 --> 00:03:21,090
Let's say n is equal to three.

46
00:03:21,090 --> 00:03:27,060
And let's say the capacity of the knapsack is eight units or w is eight.

47
00:03:27,180 --> 00:03:31,350
Now because n is equal to three we will have three items.

48
00:03:31,350 --> 00:03:36,960
So let's say the value array is 239 and the weight array is 825.

49
00:03:36,960 --> 00:03:42,510
So this means that the first item has a value of two and a weight of eight units.

50
00:03:42,510 --> 00:03:49,620
The second item has a value of three and a weight of two units, and the third item has a value of nine

51
00:03:49,620 --> 00:03:51,660
and a weight of five units.

52
00:03:52,230 --> 00:04:00,090
Now you could, for example, just pick this single item because its weight itself is eight, and the

53
00:04:00,090 --> 00:04:03,000
capacity of the knapsack is also eight.

54
00:04:03,000 --> 00:04:09,120
So in this case, the value that you've been able to add to the knapsack is equal to two.

55
00:04:09,120 --> 00:04:12,660
Now you could think of value as dollars or something like that.

56
00:04:12,660 --> 00:04:16,140
So over here in this example the value achieved is two.

57
00:04:16,140 --> 00:04:20,220
Now another approach would be to add these two items.

58
00:04:20,220 --> 00:04:27,690
Notice that the sum of these two items weights respectively is two plus five, which is seven units,

59
00:04:27,690 --> 00:04:29,490
which is still less than eight.

60
00:04:29,490 --> 00:04:34,590
And the value at this point is three plus nine, which is equal to 12.

61
00:04:36,480 --> 00:04:37,050
Okay.

62
00:04:37,050 --> 00:04:45,990
And the question asks us to pack items into the knapsack or the backpack in a way that the value is

63
00:04:45,990 --> 00:04:46,950
maximized.

64
00:04:46,950 --> 00:04:48,930
So this is the question at hand.

65
00:04:48,930 --> 00:04:55,770
And as always, remember to ask any clarifying questions that you may have when you are presented with

66
00:04:55,770 --> 00:04:57,150
the coding interview question.

67
00:04:57,150 --> 00:05:01,710
Now, a possible question over here is is it possible for n to be zero?

68
00:05:01,710 --> 00:05:02,250
No.

69
00:05:02,250 --> 00:05:05,490
Let's say the interviewer replies to you, no, that's not possible.

70
00:05:05,490 --> 00:05:07,530
N will at least be one.

71
00:05:07,620 --> 00:05:12,540
Now another question could be Will values be always be positive?

72
00:05:12,540 --> 00:05:16,860
Or could it be the case that some items have negative values?

73
00:05:16,860 --> 00:05:21,480
And let's say the interviewer replies that all the values are positive?

74
00:05:22,200 --> 00:05:25,470
All right, so we have got a good idea of the question at hand.

75
00:05:25,470 --> 00:05:28,200
Now let's go ahead and write a few test cases.

76
00:05:28,200 --> 00:05:33,810
Now remember in coding interviews you can come up with test cases along with the interviewer.

77
00:05:33,810 --> 00:05:38,250
And that's helpful to ensure that both of you are on the same page.

78
00:05:38,250 --> 00:05:44,010
Now we've already seen one example where we had three items and the values were two, three, nine,

79
00:05:44,010 --> 00:05:45,990
and the weights were eight, two, five.

80
00:05:45,990 --> 00:05:53,250
In this case, the maximum value that can be added to the backpack or the knapsack is 12, which is

81
00:05:53,250 --> 00:05:54,210
three plus nine.

82
00:05:54,210 --> 00:05:56,790
So that's the required output in this case.

83
00:05:58,400 --> 00:06:00,260
Let's take another example.

84
00:06:00,260 --> 00:06:02,330
Let's say we just have two items.

85
00:06:02,330 --> 00:06:05,840
The values are two and nine and the weights are ten and 11.

86
00:06:05,840 --> 00:06:08,930
And the capacity of the backpack is just nine.

87
00:06:08,930 --> 00:06:14,480
In this case, the output has to be zero because no item can be added to the backpack.

88
00:06:14,480 --> 00:06:18,890
So we have understood the question and we have gone through a few test cases.

89
00:06:18,890 --> 00:06:23,030
In the next video, let's try to think about how to solve this question.