Problem

Submissions

Hints & solutions

Discuss

Rod cutting problem

Moderate

0/80

Average time to solve is 40m

Contributed by

319 upvotes

Asked in companies

Problem statement

Given a rod of length ‘N’ units. The rod can be cut into different sizes and each size has a cost associated with it. Determine the maximum cost obtained by cutting the rod and selling its pieces.

Note:

1. The sizes will range from 1 to ‘N’ and will be integers.

2. The sum of the pieces cut should be equal to ‘N’.

3. Consider 1-based indexing.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next 2 * T lines represent the ‘T’ test cases.

The first line of each test case contains an integer ‘N’ denoting the length of the rod.

The second line of each test case contains a vector ’A’, of size ‘N’ representing the cost of different lengths, where each index of the array is the sub-length and the element at that index is the cost for that sub-length.

Note:

Since 1-based indexing is considered, the 0th index of the vector will represent sub-length 1 of the rod. Hence the (N - 1)th index would represent the cost for the length ‘N’.

Output Format

For each test case, print a single line that contains a single integer which is the maximum cost obtained by selling the pieces.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 100
1 <= A[i] <= 100

Where ‘T’ is the total number of test cases, ‘N’ denotes the length of the rod, and A[i] is the cost of sub-length.

Time limit: 1 sec.

Sample Input 1:

2
5
2 5 7 8 10
8
3 5 8 9 10 17 17 20

Sample Output 1:

12
24

Explanation of sample input 1:

Test case 1:

All possible partitions are:
1,1,1,1,1           max_cost=(2+2+2+2+2)=10
1,1,1,2             max_cost=(2+2+2+5)=11
1,1,3               max_cost=(2+2+7)=11
1,4                 max_cost=(2+8)=10
5                   max_cost=(10)=10
2,3                 max_cost=(5+7)=12
1,2,2               max _cost=(1+5+5)=12    

Clearly, if we cut the rod into lengths 1,2,2, or 2,3, we get the maximum cost which is 12.


Test case 2:

Possible partitions are:
1,1,1,1,1,1,1,1         max_cost=(3+3+3+3+3+3+3+3)=24
1,1,1,1,1,1,2           max_cost=(3+3+3+3+3+3+5)=23
1,1,1,1,2,2             max_cost=(3+3+3+3+5+5)=22
and so on….

If we cut the rod into 8 pieces of length 1, for each piece 3 adds up to the cost. Hence for 8 pieces, we get 8*3 = 24.

Sample Input 2:

1
6
3 5 6 7 10 12

Sample Output 2:

Hint 1

Hint 2

Hint 3

Find all the possible partitioning of the rod.

Approaches (3)

Approach 1

Approach 2

Approach 3

Recursive Approach

This is a recursive approach.
Initialize a variable ‘MAXCOST’ to INT_MIN;
In each recursive function call, run a loop where ‘I’ ranges from 0 to ‘N - 1’, and partition the rod of length ‘N’ into two parts, ‘I’ and ‘N - I’.
Example For a rod of length 5, for 'I' = 2, the two partitions will be 2 and 3.
1. Take ‘I’ as the first cut in the rod and keep it constant. Now, a rod of ‘N - I - 1’ remains. Pass the remaining rod of size ‘N - I - 1’ to the recursion.
2. Step 1 continues until it hits the base condition, which is when the length of the rod becomes zero.
3. When the recursion hits the base condition, the cost of a particular configuration is obtained.
4. Compare it with the ‘MAXCOST’ variable and store the maximum of the cost in variable ‘MAXCOST’.
For every ‘I’ as an initial sub-length, different configurations are obtained and compared to the ‘MAXCOST’ variable.
Lastly, ‘MAXCOST’ contains the final answer.

Time Complexity

O(2 ^ N), where ‘N’ is the length of the rod.

In the worst case, all possible combinations for length ‘N’ are recursively found.

Space Complexity

O(N), where ‘N’ is the length of the rod.

Recursive stack uses space of the order ‘N’.

(75% EXP penalty)

(100% EXP penalty)

Rod cutting problem

Shivam Jha

Interview problems

EASY DP MEMOIZATION SOLUTION ✅✅✅

#include <bits/stdc++.h>

int solve(int index, int target, vector<int> &nums, vector<vector<int>> &dp) {

if (index == 0)

return target * nums[0];

if (dp[index][target] != -1)

return dp[index][target];

int not_take = solve(index - 1, target, nums, dp);

int take = 0;

if (target > index)

take = nums[index] + solve(index, target - index - 1, nums, dp);

return dp[index][target] = max(take, not_take);

}

int cutRod(vector<int> &price, int n) {

vector<vector<int>> dp(n, vector<int>(n + 1, -1));

return solve(n - 1, n, price, dp);

}

168 views

0 replies

2 upvotes

Shivam Jha

Interview problems

EASY DP TABULATION ✅✅✅

#include <bits/stdc++.h>

int cutRod(vector<int> &price, int n) {

vector<vector<int>> dp(n, vector<int>(n + 1, 0));

for (int i = 0; i <= n; i++) {

dp[0][i] = i * price[0];

}

for (int i = 1; i < n; i++) {

for (int target = 0; target <= n; target++) {

int not_take = dp[i - 1][target];

int take = 0;

if (target > i)

take = price[i] + dp[i][target - i - 1];

dp[i][target] = max(take, not_take);

}

return dp[n - 1][n];

}

72 views

0 replies

1 upvote

Kartik Choudhary

Interview problems

java solution

import java.util.Arrays;

public class Solution {

public static int cutRod(int price[], int n) {

int prev[] = new int[n+1];

for(int N=0; N<=n;N++){

prev[N] = N*price[0];

}

for(int ind = 1; ind<n ; ind++){

for(int N = 0; N<=n ; N++){

int notTake = 0 + prev[N];

int rodLength = ind + 1;

int take = Integer.MIN_VALUE;

if(rodLength<= N) take = price[ind] + prev[N-rodLength];

prev[N] = Math.max(notTake , take);

}

// Write your code here.

return prev[n];

}

59 views

0 replies

0 upvotes

Alok Nayak

Interview problems

c++ solution

int cutRod(vector<int> &p, int n)
{
	vector<int> v(n+1,0);
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			v[j]=max(v[j-i]+p[i-1],v[j]);
		}
	}
	return v[n];
}

129 views

0 replies

0 upvotes

Manav Shailendra Lade

Interview problems

EASY JAVA SOLUTION USING DYNAMIC PROGRAMMING

public static int cutRod(int price[], int n) {
		int [] dp = new int[n+1];

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < i; j++) {
				dp[i] = Math.max(dp[i], price[j] + dp[i-j-1]);
			}
		}
		return dp[n];
	}

57 views

0 replies

1 upvote

Nisha Anand

Interview problems

Tabulation



int maxcostTab(vector<int> &price, int n){
    vector<int> dp(n+1, 0);



    //iterating for every rod length
    for(int j = 1; j<=n; j++){
    //here i is how much i am cutting from the rod
    for(int i=1; i<=j; i++){
        
        dp[j] = max(dp[j],dp[j-i] + price[i-1]);
    
    }
    }
    return dp[n];
}

Time complexity - O(n^2)
space complexity - O(n)

62 views

0 replies

0 upvotes

Adarsh

Interview problems

unbounded knapsack

52 views

0 replies

0 upvotes

Harshit

Interview problems

C++ | 1D DP Recursive | Simple

int helper(vector<int>& price,int n,vector<int>& dp){

if(n==1){

return price[0];

}

if(n==0){

return 0;

}

if(dp[n] != -1){

return dp[n];

}

int ans = 0;

for(int i = 1; i<=n; i++){

ans = max(ans,price[i-1]+helper(price,n-i,dp));

}

return dp[n] = ans;

}

int cutRod(vector<int> &price, int n){

vector<int> dp(n+1,-1);

return helper(price,n,dp);

}

96 views

0 replies

0 upvotes

Manul Chourasia

Interview problems

C++ solution in time O(n^2) and space O(n)

int cutRod(vector<int> &p, int n)
{
	vector<int> v(n+1,0);
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			v[j]=max(v[j-i]+p[i-1],v[j]);
		}
	}
	return v[n];
}

77 views

0 replies

0 upvotes

KARTIK

Interview problems

Java Solution : RECURSION || MEMORISATION || TABULATION :: Space Optimization

public class Solution {

##RECURSIVE

public static int cutRod(int price[], int T, int ind) {

// Write your code here.

if(ind == 0) return T*price[0];

int notTake = cutRod(price, T, ind-1);

int Take = (T >= (ind+1)) ? price[ind] + cutRod(price, (T-(ind+1)), ind) : Integer.MIN_VALUE;

return Math.max(notTake, Take);

}

public static int cutRod(int price[], int n) {

// Write your code here.

return cutRod(price, n, price.length-1);

}

##MEMORIZATION

public static int cutRod(int price[], int T, int ind, int[][] dp) {

// Write your code here.

if(ind == 0) return T*price[0];

if(dp[ind][T] != 0) return dp[ind][T];

int notTake = cutRod(price, T, ind-1, dp);

int Take = (T >= (ind+1)) ? price[ind] + cutRod(price, (T-(ind+1)), ind, dp) : Integer.MIN_VALUE;

return dp[ind][T] = Math.max(notTake, Take);

}

public static int cutRod(int price[], int n) {

// Write your code here.

int[][] dp = new int[n][n+1];

return cutRod(price, n, n-1, dp);

}

##TABULATION

public static int cutRod(int price[], int n) {

// Write your code here.

int[][] dp = new int[n][n+1];

for(int T = 0; T <= n; T++){

dp[0][T] = T*price[0];

}

for(int ind = 1; ind < n; ind++){

for(int T = 0; T <= n; T++){

int notTake = dp[ind-1][T];

int Take = (T >= (ind+1)) ? price[ind] + dp[ind][T-(ind+1)] : Integer.MIN_VALUE;

dp[ind][T] = Math.max(notTake, Take);

}

return dp[n-1][n];

}

##SPACE OPTIMIZATION

public static int cutRod(int price[], int n) {

// Write your code here.

int[] dp = new int[n+1];

for(int T = 0; T <= n; T++){

dp[T] = T*price[0];

}

for(int ind = 1; ind < n; ind++){

for(int T = 0; T <= n; T++){

int notTake = dp[T];

int Take = (T >= (ind+1)) ? price[ind] + dp[T-(ind+1)] : Integer.MIN_VALUE;

dp[T] = Math.max(notTake, Take);

}

return dp[n];

}

115 views

0 replies

0 upvotes

Console