Here is my tabulation approach for this problem. Some may find it easier if they would have gone through the previous videos in this playlist. Here rod_len is as same as that of capacity in knapsack and n is the size of the length array. Here one thing is to note that if length array is like {1,2,4,5,7,9}(it means we can cut array in pieces of lengths 1,2,4,5,7,9) and rod_length is 9 then n value will be 6 not 9. int rod_cutting(int price[],int length[],int rod_len,int n){ int dp[n+1][rod_len+1]; for(int i=0;i
@TECH DOSE , sir, In code why are you not checking if the subproblem is already solved (that's the main purpose of memoisation). you are just storing it in mem but not using it except for the end (return mem[N][maxLen]). Why?
Sir ! i feel like there is a lot of similarity to coin change and this problem like coins=cuts target=max_len n=n but here we are just maximizing the profit ???
I am just giving a try to tabulation approach -- not sure what's wrong. def rodCutting(price, W, N): DP = [[0 for x in range(W+1)] for j in range(N+1)]
for i in range(0, N+1): DP[i][0] = 1 for i in range(1, N+1): for j in range(1, W+1): if j < price[i-1]: DP[i][j] = DP[i-1][j] else: DP[i][j] = max(DP[i-1][j],price[i-1]+DP[i][j-price[i-1]]) return DP[-1][-1]
In the DP table, the sub problems where we evaluate for rod length = 0, how can any profit be realized? There is no rod to cut. The code snippet :- for i in range(0,N+1): DP[i][0] = 1 Change that 1 to 0. Also here, within the inner for loop, else condition: the case where we cut the rod by the given length, we have to do dp[i][j-length[i-1]] and not dp[i][j-prices[i-1]]
01 property is always present for all types of integer knapsack. 01 knapsack will mean that you can't have 2 sub-rods of the same length which is not true. You can have unlimited number of sub-rods of the same length as long as the rod doesn't finish. It's not bounded knapsack because we don't have any hard limit on number of sub-rods of a given length. I hope you got it.
Hi Surya.pratap.k, Amazing video series. you are awesome!!. can you please explain leet code#698 and relate to this playlist so far? what happens if the array has duplicate elements in it and can we still apply the grid approach?
The problem of overlapping sub-problems is not solved. In the mem array, the same result gets recomputed again and again instead of simply returning the previously calculated result. Please explain how is this issue being resolved.
Here is my tabulation approach for this problem. Some may find it easier if they would have gone through the previous videos in this playlist. Here rod_len is as same as that of capacity in knapsack and n is the size of the length array. Here one thing is to note that if length array is like {1,2,4,5,7,9}(it means we can cut array in pieces of lengths 1,2,4,5,7,9) and rod_length is 9 then n value will be 6 not 9.
int rod_cutting(int price[],int length[],int rod_len,int n){
int dp[n+1][rod_len+1];
for(int i=0;i
exactly what i think
You have got the skill to explain the concept very well. Thank you for doing this. Also, which software do you use for this kind of presentation?
Mate where have you been for God sake? I've stuck on this problem for long time. Many thanks
Welcome 😀
Awesome way of Teaching . Got the concept very easily . Thank You So Much for providing us with valuable content 😍
07:14 Sir if we take i from 1 to N then it should be price[i-1]+CutRod(N-i). because price[n] is not defined.
@TECH DOSE , sir, In code why are you not checking if the subproblem is already solved (that's the main purpose of memoisation).
you are just storing it in mem but not using it except for the end (return mem[N][maxLen]). Why?
I think it's a typo, but the concept was referred to the same If you refer to his (0/1) explanation.
My alternative recursive solution without using the for loop:
int maxProfitRodCutting (vector length, vector profit, int n, int target)
{
if (target
Sir ! i feel like there is a lot of similarity to coin change and this problem like
coins=cuts
target=max_len
n=n
but here we are just maximizing the profit ???
What is the difference between N and maxlen. N is length of rod, so it should be 4, what is maxlen?
Dear techdose, all the solutions explained so far takes O(N*W) space. How can we reduce it to O(W) space? Thanks in advance
See if you need only the previous state then you can maintain 1D array and do it
I am just giving a try to tabulation approach -- not sure what's wrong.
def rodCutting(price, W, N):
DP = [[0 for x in range(W+1)] for j in range(N+1)]
for i in range(0, N+1):
DP[i][0] = 1
for i in range(1, N+1):
for j in range(1, W+1):
if j < price[i-1]:
DP[i][j] = DP[i-1][j]
else:
DP[i][j] = max(DP[i-1][j],price[i-1]+DP[i][j-price[i-1]])
return DP[-1][-1]
In the DP table, the sub problems where we evaluate for rod length = 0, how can any profit be realized? There is no rod to cut. The code snippet :-
for i in range(0,N+1):
DP[i][0] = 1
Change that 1 to 0.
Also here, within the inner for loop, else condition: the case where we cut the rod by the given length, we have to do dp[i][j-length[i-1]] and not dp[i][j-prices[i-1]]
Awesome explanation, great job TECH DOSE!
Thanks :)
Bro it's same as 0)1 bounded knap sack right? What's the difference?
It is Unbounded knapsack. Already explained why in the video. Also explained in one of the comment. Please watch it.
Thank you for the amazing work
I think it's not unbounded knapsack because in the recursive solution an instance is excluded or included 01
01 property is always present for all types of integer knapsack. 01 knapsack will mean that you can't have 2 sub-rods of the same length which is not true. You can have unlimited number of sub-rods of the same length as long as the rod doesn't finish. It's not bounded knapsack because we don't have any hard limit on number of sub-rods of a given length. I hope you got it.
Hi Surya.pratap.k, Amazing video series. you are awesome!!. can you please explain leet code#698 and relate to this playlist
so far? what happens if the array has duplicate elements in it and can we still apply the grid approach?
I dint see the question. I will check it once I get some time.
Thank you sir
Welcome
amazing bro!!!
Thanks
He is your sir not bro😂
Isn't that p[i+1] ? since the new range is [0,n-1)
max(maxprofit(profit[],len[],i+1),profit[i]+maxprofit(profit[],len[],i+1))
will this work ?
base case
i==length of rod
return 0
You also have to pass N, which is the upper bound of the array length, otherwise you will get segmentation fault.
How maxlen is our maximum capacity, like we want and can have as much price we can?
here, maxlen is the length of the rod. We can cut a rod of length 4 any number of times but cannot cut it for a length greater than 4, haina?
@@saptarshidas488 exactly
max len refers to what and n refers to what pls expalin i cant understand
Maxlen is the capacity of bag. Please watch 01 knapsack video using memoization and then come back to understand this. It will be easier.
Shrey sir OP🔥
The problem of overlapping sub-problems is not solved. In the mem array, the same result gets recomputed again and again instead of simply returning the previously calculated result. Please explain how is this issue being resolved.
I guess it's because he forgot to return the value if it's already present. He's just adding it into the table but not using it when needed.
make video on jump game problem
I think it's made. Check it once.
@@techdose4u already made
sir i can't find anywhere on internet where i can submit this
This is present in geeksforgeeks and a harder variation is present on interviewbits dp section.
@@techdose4u ok sir
Ok and ok
seems to complex explanation :l
:)
:)
pls reply sir
Replied
@@techdose4u lol