Rod Cutting Problem | Dynamic Programming | Unbounded Knapsack

[@kr_ankit123]

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

[@saravana6882]

exactly what i think

[@mrboyban]

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

[@techdose4u]

Welcome 😀

[@mohammadumaidansari5087]

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

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

[@gautamsuthar4143]

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.

[@ashishkhoiwal9330]

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

[@vijethpatil3044]

I think it's a typo, but the concept was referred to the same If you refer to his (0/1) explanation.

[@alessandrocamilleri1239]

My alternative recursive solution without using the for loop: int maxProfitRodCutting (vector length, vector profit, int n, int target) { if (target

[@Usurperhk]

Awesome explanation, great job TECH DOSE!

[@techdose4u]

Thanks :)

[@sainikhil956]

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

[@ganeshkamath89]

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

[@diptiranjandash8877]

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]

[@saptarshidas488]

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

[@mykolapetriv2017]

Thank you for the amazing work

[@dayanandraut5660]

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

[@techdose4u]

See if you need only the previous state then you can maintain 1D array and do it

[@pleasesirmorevideos4684]

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

[@techdose4u]

This is present in geeksforgeeks and a harder variation is present on interviewbits dp section.

[@pleasesirmorevideos4684]

@@techdose4u ok sir

[@RTX_valorant]

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

[@techdose4u]

It is Unbounded knapsack. Already explained why in the video. Also explained in one of the comment. Please watch it.

[@syedkaja2045]

amazing bro!!!

[@techdose4u]

Thanks

[@pleasesirmorevideos4684]

He is your sir not bro😂

[@E__ShameemahamedS-bx2ed]

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

[@techdose4u]

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.

[@priestj3125]

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?

[@techdose4u]

I dint see the question. I will check it once I get some time.

[@E__ShameemAhamedS]

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

[@techdose4u]

Maxlen is the capacity of bag. Please watch 01 knapsack video using memoization and then come back to understand this. It will be easier.

[@Dankman3]

Thank you sir

[@techdose4u]

Welcome

[@kshitijgaur9635]

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.

[@krishjani2103]

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.

[@hayyaun]

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

[@gourav.barkle]

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

[@saptarshidas488]

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?

[@harcharansingh1997]

@@saptarshidas488 exactly

[@syedkaja2045]

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

[@spetsnaz_2]

You also have to pass N, which is the upper bound of the array length, otherwise you will get segmentation fault.

[@anshuhimanshusuthar5614]

Shrey sir OP🔥

[@syedkaja2045]

make video on jump game problem

[@techdose4u]

I think it's made. Check it once.

[@spetsnaz_2]

@@techdose4u already made

[@NishantSharma-sz5xh]

Ok and ok

[@shubhamgomase9056]

seems to complex explanation :l

[@TomerBenDavid]

:)

[@techdose4u]

:)

[@E__ShameemAhamedS]

pls reply sir

[@techdose4u]

Replied

[@RTX_valorant]

@@techdose4u lol