Rod Cutting Problem | Dynamic Programming | Unbounded Knapsack

This video explains a very important programming interview problem which is the rod cutting problem.This is a famous dynamic programming problem which is very frequently asked in interviews and coding rounds.This problem is the same as unbounded knapsack problem.I have explained the problem statement using examples and shown the solution idea and the recursion solution with time complexity.I have then shown optimization needed to solve using dynamic programming. I have shown the code and algorithm for dynamic programming solution.This has polynomial time complexity. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by JOINING and SUBSCRIBING. LIKE and SHARE our video if you found it helpful...CYA :)

========================================================================
Join this channel to get access to perks:

=======================================================================

USEFUL LINKS:-

#dp #unboundedknapsack #rodcutting

[kr_ankit]

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<=n;i++){
for(int j=0;j<=rod_len;j++){
if(j==0){
dp[i][j]=0;
}
else if(i==0){
dp[i][j]=0;
}
else if(j< length[i-1]){
dp[i][j]= dp[i-1][j];
}
else{
dp[i][j]= max(price[i-1]+dp[i][j-length[i-1]], dp[i-1][j]);
}
}
}

return dp[n][rod_len];
}

[mrboyban]

Mate where have you been for God sake? I've stuck on this problem for long time. Many thanks

[therohitpatil]

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?

[ashishkhoiwal]

@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?

[gautamsuthar]

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.

[mohammadumaidansari]

Awesome way of Teaching . Got the concept very easily . Thank You So Much for providing us with valuable content 😍

[alessandrocamilleri]

My alternative recursive solution without using the for loop:

int maxProfitRodCutting (vector<int> length, vector<int> profit, int n, int target)
{
if (target <= 0 || n <0) return 0;
int included = maxProfitRodCutting (length, profit, n, target - length[n]);
int excluded = maxProfitRodCutting (length, profit, n - 1, target);
if (length[n] <= target)
included += profit[n];
return max (included, excluded);
}

[sainikhil]

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 ???

[ganeshkamath]

What is the difference between N and maxlen. N is length of rod, so it should be 4, what is maxlen?

[dayanandraut]

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

[RTX_valorant]

Bro it's same as 0)1 bounded knap sack right? What's the difference?

[diptiranjandash]

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]

[Usurperhk]

Awesome explanation, great job TECH DOSE!

[syedkaja]

max(maxprofit(profit[], len[], i+1), profit[i]+maxprofit(profit[], len[], i+1))
will this work ?
base case
i==length of rod
return 0

[E__ShameemahamedS-bxed]

I think it's not unbounded knapsack because in the recursive solution an instance is excluded or included 01

[kshitijgaur]

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.

[gourav.barkle]

How maxlen is our maximum capacity, like we want and can have as much price we can?

[E__ShameemAhamedS]

max len refers to what and n refers to what pls expalin i cant understand

[pleasesirmorevideos]

sir i can't find anywhere on internet where i can submit this

[hayyanhami]

Isn't that p[i+1] ? since the new range is [0, n-1)