1
00:00:00,110 --> 00:00:01,100
Welcome back.

2
00:00:01,250 --> 00:00:07,040
In this video, let's get started with another interesting coding interview question, which is called

3
00:00:07,040 --> 00:00:09,260
the Unbounded Knapsack question.

4
00:00:09,650 --> 00:00:17,000
The question reads you are given a set of n items, each with a weight and a value represented by the

5
00:00:17,000 --> 00:00:23,600
array w, t, and val respectively, and a knapsack with weight limit w.

6
00:00:23,960 --> 00:00:32,720
The task is to fill the knapsack in such a way that we can get the maximum profit return the maximum

7
00:00:32,720 --> 00:00:34,640
profit, okay, and it says.

8
00:00:34,640 --> 00:00:38,270
Note each item can be taken any number of times.

9
00:00:38,270 --> 00:00:43,310
So this is how this question is different from the zero one knapsack problem which we have previously

10
00:00:43,310 --> 00:00:43,850
discussed.

11
00:00:43,850 --> 00:00:46,490
So over here we're given an example.

12
00:00:46,490 --> 00:00:49,580
So let's say we are given just two items.

13
00:00:49,580 --> 00:00:53,870
And the value of those two items are five and ten respectively.

14
00:00:53,870 --> 00:00:57,020
And their respective weights are two and two.

15
00:00:57,020 --> 00:00:57,440
Okay.

16
00:00:57,440 --> 00:01:05,330
Now if this is the case and if the maximum capacity of the given knapsack is six units of weight, then

17
00:01:05,330 --> 00:01:11,270
the required output would be 30, because you can just take three of these items okay.

18
00:01:11,270 --> 00:01:15,440
So if this is item one and let's say this is item two okay.

19
00:01:15,440 --> 00:01:20,750
So you can just fill three units of item two into the knapsack.

20
00:01:20,750 --> 00:01:24,620
So you have a knapsack and you have item two.

21
00:01:24,620 --> 00:01:26,150
And again you have item two.

22
00:01:26,150 --> 00:01:28,520
And again you have item two okay.

23
00:01:28,520 --> 00:01:33,770
Now notice that the value of the items in the knapsack is ten plus ten plus ten.

24
00:01:33,770 --> 00:01:36,170
Because each item has a value of ten.

25
00:01:36,170 --> 00:01:41,600
And at this point, the total value of the items in the knapsack is equal to 30.

26
00:01:41,600 --> 00:01:45,260
And this is the desired output as per the question.

27
00:01:45,260 --> 00:01:51,290
And again at this point, notice that the total weight of the items in the knapsack is two plus two

28
00:01:51,290 --> 00:01:54,680
plus two, which is less than or equal to six.

29
00:01:54,680 --> 00:01:56,780
So this is the condition given in the question.

30
00:01:56,780 --> 00:01:58,130
And this is actually six.

31
00:01:58,130 --> 00:02:00,170
And six is less than or equal to six.

32
00:02:00,170 --> 00:02:01,970
So the condition is also satisfied.

33
00:02:01,970 --> 00:02:03,680
So this is the question at hand.

34
00:02:03,680 --> 00:02:07,220
In the next video let's discuss how we can solve this question.