1
00:00:01,020 --> 00:00:02,969
Hi, everyone, welcome to this new video.

2
00:00:03,000 --> 00:00:08,310
So in this video, what we are going to do is we are going to convert our recursive code into a dynamic

3
00:00:08,310 --> 00:00:09,100
programming code.

4
00:00:09,690 --> 00:00:14,180
So, first of all, let us first figure out whether our dynamic programming will be upgraded, appear

5
00:00:14,280 --> 00:00:14,940
to be.

6
00:00:15,480 --> 00:00:21,370
So here we can see a number of items changing in the current call and the way it is also changing in

7
00:00:21,370 --> 00:00:21,980
direction.

8
00:00:22,620 --> 00:00:25,860
So two things are changing in the casting call.

9
00:00:26,040 --> 00:00:30,060
So that's why this is basically to really be so to Redzepi.

10
00:00:30,060 --> 00:00:34,320
I mean, we need to create metrics to solve this problem, right.

11
00:00:34,680 --> 00:00:36,250
So that is the meaning of the GDP.

12
00:00:36,270 --> 00:00:41,220
So it's very simple to figure out whether a given problem will be solved by one dimensionality, one

13
00:00:42,360 --> 00:00:43,600
or two dimensional debris.

14
00:00:43,830 --> 00:00:47,400
You just need to figure out how many things are changing in your current goal.

15
00:00:47,640 --> 00:00:49,470
So here two things are changing.

16
00:00:49,740 --> 00:00:53,010
Number of items is changing and the weight of your knapsack is changing.

17
00:00:53,010 --> 00:00:55,110
So that's why this is two dimensional dippie.

18
00:00:55,740 --> 00:00:56,130
Right.

19
00:00:56,340 --> 00:00:58,900
So we have figured out this is a two dimensional leap.

20
00:00:59,040 --> 00:01:01,260
Now in this two dimensional leap.

21
00:01:04,690 --> 00:01:11,470
Since a number of items is changing and we're talking about is changing, so at one side we will have

22
00:01:11,650 --> 00:01:16,240
a number of items changing and here we will have the weight of your knapsack changing.

23
00:01:17,080 --> 00:01:17,510
Right.

24
00:01:17,530 --> 00:01:20,150
So we start from zero, so will start from zero.

25
00:01:20,320 --> 00:01:29,350
So what deep of AIJA represent so what DPI, Gippsland, DPI represent the maximum profit that you can

26
00:01:29,350 --> 00:01:32,050
earn by taking items.

27
00:01:33,980 --> 00:01:40,340
And when the weight of your knapsack is the weight of your bag, is J.A.G., right?

28
00:01:40,520 --> 00:01:43,940
So according to this definition, what will be our answer?

29
00:01:43,940 --> 00:01:47,580
Our answer will be deep of any number of items and the total weight.

30
00:01:47,960 --> 00:01:54,560
So what will be the value of this, the maximum profit that you can earn by considering any items?

31
00:01:54,950 --> 00:02:00,050
That is the total number of items and considering the weight of your bag to be WTG.

32
00:02:00,680 --> 00:02:01,030
Right.

33
00:02:01,040 --> 00:02:03,740
And that is we need to figure out.

34
00:02:03,740 --> 00:02:04,860
That will be our answer.

35
00:02:04,880 --> 00:02:11,780
So our answer will be the value that we present at the last at this basically at this box, right in

36
00:02:11,780 --> 00:02:12,320
this box.

37
00:02:13,520 --> 00:02:15,040
Now, let's talk about biscuits.

38
00:02:15,380 --> 00:02:22,730
So if the number of items is zero, so if the number of items is basically zero, then the profit will

39
00:02:22,730 --> 00:02:23,200
be zero.

40
00:02:25,760 --> 00:02:31,400
Similarly, if the weight of your bag, if the weight of your knapsack back is zero, then your profit

41
00:02:31,400 --> 00:02:32,000
will be zero.

42
00:02:33,950 --> 00:02:34,400
Right.

43
00:02:34,580 --> 00:02:41,450
And for this, we have recursive relations so we can convert them easily into the code.

44
00:02:41,930 --> 00:02:43,310
So now we have everything.

45
00:02:43,310 --> 00:02:44,720
Let's start writing the code.

46
00:02:45,290 --> 00:02:48,650
So first of all, let us figure out the number of items.

47
00:02:48,650 --> 00:02:51,160
So a number of items is price, not size.

48
00:02:52,580 --> 00:02:53,030
Right.

49
00:02:53,300 --> 00:02:54,950
And let's command this line.

50
00:02:57,300 --> 00:03:08,160
So we know the number of items and now we need to create one deepti of size and plus one and the blue

51
00:03:08,280 --> 00:03:10,180
plus one word of an harpsichords W..

52
00:03:10,200 --> 00:03:14,670
So this will be our two time period because things are changing.

53
00:03:14,940 --> 00:03:21,360
And as discussed, my answer will be the payoff and the maximum profit that I can by considering a number

54
00:03:21,360 --> 00:03:24,360
of items when the weight of my bag is W.

55
00:03:26,030 --> 00:03:28,270
Now we need to fill this deep area.

56
00:03:28,300 --> 00:03:34,630
So let's start iterating over this deputy to fill this area.

57
00:03:34,730 --> 00:03:36,800
So let's do that.

58
00:03:42,160 --> 00:03:46,990
Glastonbury, close to the weight of the is W and J plus plus.

59
00:03:48,920 --> 00:03:53,390
So if the number of items is zero.

60
00:03:54,460 --> 00:04:00,310
Or the weight of your bag is zero in that case, what will be your profit?

61
00:04:00,640 --> 00:04:01,990
Your profit will be zero.

62
00:04:02,470 --> 00:04:03,660
This is the best case.

63
00:04:04,630 --> 00:04:08,710
Your profit is going to be zero, right?

64
00:04:09,880 --> 00:04:11,470
In the elusive part.

65
00:04:12,550 --> 00:04:14,940
Let's talk about the second condition, right.

66
00:04:14,950 --> 00:04:20,300
This one, if the weight of the item is greater than the weight of the knapsack.

67
00:04:21,190 --> 00:04:34,390
So if the weight of the item, if the weight of item is greater than the weight of knapsack, in that

68
00:04:34,390 --> 00:04:36,220
case, you cannot pick this item.

69
00:04:36,850 --> 00:04:38,540
So what will be your answer?

70
00:04:39,190 --> 00:04:48,850
Your answer will be, since we cannot pick this item so DPF reduce the number of items and your knapsack

71
00:04:48,850 --> 00:04:49,990
rate will remain same.

72
00:04:51,580 --> 00:04:52,000
Right?

73
00:04:53,170 --> 00:05:01,270
So one thing to notice here is here you need to write a minus one because when the value of five will

74
00:05:01,270 --> 00:05:07,450
become ln, this value will become weight off and right.

75
00:05:07,450 --> 00:05:10,600
And which is wrong because the last index will be in minus one.

76
00:05:11,170 --> 00:05:15,270
So when I'm saying weight of item, the weight of a little item.

77
00:05:15,520 --> 00:05:20,470
So that means you need to write a minus one here because indexing starts some zero weight.

78
00:05:29,100 --> 00:05:31,350
So what I've done here is.

79
00:05:34,420 --> 00:05:36,130
I have written this line.

80
00:05:38,020 --> 00:05:48,220
Here right now, we need to convert this party into binding programming code, so in the Elzbieta in

81
00:05:48,220 --> 00:05:50,980
the LS part, I can pick this item right?

82
00:05:51,370 --> 00:05:52,540
I can pick this item.

83
00:05:52,540 --> 00:05:53,530
So I have two option.

84
00:05:54,040 --> 00:05:57,100
Either pick this item and find out the maximum profit.

85
00:05:57,820 --> 00:06:04,450
Second option is do not pick this item, exclude this item and try to find out the maximum profit.

86
00:06:04,630 --> 00:06:06,420
And what will be your answer.

87
00:06:06,700 --> 00:06:15,520
Your answer will be the maximum of when you pick this item, the maximum profit, and similarly exclude

88
00:06:15,520 --> 00:06:20,650
when you exclude this item, when you do not pick the current item so far, including what I will do,

89
00:06:20,800 --> 00:06:23,980
I will get the price of the item.

90
00:06:25,630 --> 00:06:26,620
What is this?

91
00:06:27,970 --> 00:06:29,940
So I am including this item.

92
00:06:29,980 --> 00:06:31,700
So how much money I will get.

93
00:06:32,170 --> 00:06:36,790
I will get the price of any item and the price of eight items.

94
00:06:36,790 --> 00:06:38,020
Prizefighting minus one.

95
00:06:38,440 --> 00:06:41,650
Similarly, what will happen since I have picked this item.

96
00:06:41,830 --> 00:06:43,930
So the number of items will reduce by one.

97
00:06:44,170 --> 00:06:50,110
And since I have this item, so the weight of my knapsack, the weight of my knapsack will decrease.

98
00:06:50,410 --> 00:06:52,690
So the weight of my knapsack was G.

99
00:06:52,990 --> 00:06:59,260
So and the weight of eight items is very toffy, minus one.

100
00:06:59,680 --> 00:07:00,090
Right.

101
00:07:00,250 --> 00:07:04,960
So what I am doing here is no, since I am picking this item.

102
00:07:04,960 --> 00:07:11,440
So the number of items will reduce by one, and since I am picking these items at the weight of my knapsack

103
00:07:11,440 --> 00:07:12,030
will decrease.

104
00:07:12,050 --> 00:07:16,930
So currently the weight of knapsack was G and the weight of eight items is very tough.

105
00:07:16,930 --> 00:07:17,620
I minus one.

106
00:07:17,890 --> 00:07:23,650
So that will be, this will be my new weight of knapsack and excluding.

107
00:07:23,650 --> 00:07:29,740
So if I exclude this then the money that I will get will be zero because I am not picking this item.

108
00:07:29,950 --> 00:07:38,380
So zero plus DPF, I am not picking these items for the number of items reduced by one, and since I

109
00:07:38,380 --> 00:07:39,340
am not picking the item.

110
00:07:39,350 --> 00:07:43,380
So no change on the capacity of your bag.

111
00:07:43,840 --> 00:07:44,150
Right.

112
00:07:44,500 --> 00:07:48,870
So yes, that is the complete code you need to write that.

113
00:07:48,940 --> 00:07:50,260
Is it very, very simple.

114
00:07:51,250 --> 00:07:51,670
Right.

115
00:07:52,450 --> 00:07:56,590
So let's see how we are able to convert everything else according to the code.

116
00:07:56,800 --> 00:07:57,760
So it's very simple.

117
00:07:57,760 --> 00:08:03,430
What I'm thinking here is if the weight of the eight item is greater than the knapsack weight, then

118
00:08:03,430 --> 00:08:04,810
you cannot pick this item.

119
00:08:04,810 --> 00:08:10,720
So the number of items reduced by one and the knapsack, which will remain same when you can pick this

120
00:08:10,720 --> 00:08:14,410
item, you have to option either include this item or exclude this item.

121
00:08:14,410 --> 00:08:19,060
So when I am including the item, the money that I will get is the price of item.

122
00:08:19,240 --> 00:08:26,650
So price of item then the number of items reduced by one because you have to one item and the weight

123
00:08:26,650 --> 00:08:28,030
of a knapsack will decrease.

124
00:08:28,030 --> 00:08:32,350
The capacity of a knapsack will decrease because you have picked eight items.

125
00:08:32,350 --> 00:08:39,130
So the current capacity minus the weight of the eight item and when you are excluding so when we are

126
00:08:39,130 --> 00:08:42,400
excluding, we just are reducing the number of items.

127
00:08:42,700 --> 00:08:46,450
So we are reducing the number of items to be a minus one.

128
00:08:46,570 --> 00:08:50,830
And finally, what we need to do, we need to take the maximum of include and exclude.

129
00:08:51,460 --> 00:08:52,780
And that will be our answer.

130
00:08:52,790 --> 00:08:54,820
And finally, we are returning our answer.

131
00:08:55,450 --> 00:08:57,610
So let's see whether this will work or not.

132
00:08:57,610 --> 00:09:00,250
Let's try to test our code and then we will submit.

133
00:09:05,680 --> 00:09:07,470
Sara Gold is working fine now.

134
00:09:07,480 --> 00:09:08,650
Let's amitava our gold.

135
00:09:16,180 --> 00:09:23,350
So, yeah, our goal is working fine, and now let's discuss time and space complexity for this solution.

136
00:09:25,500 --> 00:09:31,920
So it's very obvious what is the time, complexity, so the time complexity is basically what you are

137
00:09:31,920 --> 00:09:34,020
doing, you are trading time.

138
00:09:34,020 --> 00:09:38,110
Complexity is number of items multiplied by the weight of your knapsack.

139
00:09:38,550 --> 00:09:40,340
Similarly, what is your space complexity?

140
00:09:40,350 --> 00:09:44,010
You are creating this two dimensional area to solve your problems.

141
00:09:44,080 --> 00:09:47,950
The number of items multiplied by the weight of your knapsack back.

142
00:09:48,630 --> 00:09:49,020
Right.

143
00:09:49,260 --> 00:09:51,480
So this is the time and the space complexity.

144
00:09:51,720 --> 00:09:56,070
Now, understanding this problem is very, very important because many problems in dining programming

145
00:09:56,070 --> 00:10:00,600
can be solved with the help of the approach that we have used here.

146
00:10:00,930 --> 00:10:01,350
Right.

147
00:10:01,590 --> 00:10:07,380
So many problems in dining programming can be solved with the help of this problem.

148
00:10:07,380 --> 00:10:11,730
If you know the approach for solving you know what knapsack, then many problems are there that are

149
00:10:11,730 --> 00:10:14,190
directly just the variation of an abstract problem.

150
00:10:14,340 --> 00:10:15,960
You just need to identify that.

151
00:10:15,960 --> 00:10:18,160
Yeah, this is simply the variation.

152
00:10:18,540 --> 00:10:19,980
So one more thing.

153
00:10:20,250 --> 00:10:26,220
As I discussed in the previous video, if we have a finite number of items, then what we need to do.

154
00:10:26,460 --> 00:10:31,830
So I told you, instead of reducing the number of items you will take and here similarly, if you have

155
00:10:31,850 --> 00:10:38,010
infinite number of items in the programming code, instead of reducing the number of items you will

156
00:10:38,010 --> 00:10:39,470
write DPF, I hear.

157
00:10:40,170 --> 00:10:45,990
So that is the only thing that will change if you have infinite copies of each item.

158
00:10:48,060 --> 00:10:53,790
So this is it that I want to cover in this video dynamic programming code for zero, you don't want

159
00:10:53,790 --> 00:10:55,140
an abstract problem, right?

160
00:10:55,140 --> 00:10:59,540
So if you have any doubt in this video, in this problem, do reach out to me.

161
00:10:59,550 --> 00:11:01,200
I will be more than happy to help you out.

162
00:11:01,230 --> 00:11:02,960
So this is all about this video.

163
00:11:02,970 --> 00:11:04,260
I will see you in the next one.

164
00:11:04,290 --> 00:11:04,860
Thank you.