Rod Cutting Problem

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 )

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:

Approach - Bottom Up

Similarly make solution

public class Solution {
	public static int cutRod(int price[], int n) {
		// Write your code here.
		int[][] dp = new int[n][n+1];
 
		for (int i = 0; i <= n; i++)
			dp[0][i] = i*price[0];
 
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= n; j++) {
				int notTake = dp[i-1][j];
				int take = Integer.MIN_VALUE;
				int rodLength = i+1;
				if (rodLength <= j)
					take = price[i] + dp[i][j-rodLength];
				dp[i][j] = Math.max(take, notTake);
			}
		}
 
		return dp[n-1][n];
	}
}

Approach - Memoization

Convert the same to memoization
Reason why n+1 is because that is length so it can go till n so array length would be n+1

public class Solution {
	public static Integer[][] dp;
	public static int cutRod(int price[], int n) {
		// Write your code here
		dp = new Integer[n][n+1];
		return dfs(price, 0, n);
	}
 
	public static int dfs(int[] prices, int i, int remaining) {
		if (i == prices.length) return 0;
 
		if (dp[i][remaining] != null) return dp[i][remaining];
 
		int notTake = dfs(prices, i+1, remaining);
		int take = 0;
		if (i + 1 <= remaining)
			take = prices[i] + dfs(prices, i, remaining - (i+1));
 
		return dp[i][remaining] = Math.max(take,notTake);
	}
}

Approach - Recursion

there are 2 options either we can take or not if we take we add the price
Why take i + 1 is because array is 0 index while remaining is for the length

public class Solution {
	public static int cutRod(int price[], int n) {
		// Write your code here.
		return dfs(price, 0, n);
	}
 
	public static int dfs(int[] prices, int i, int remaining) {
		if (i == prices.length) return 0;
 
		int notTake = dfs(prices, i+1, remaining);
 
		int take = 0;
		if (i + 1 <= remaining)
			take = prices[i] + dfs(prices, i, remaining - (i+1));
 
		return Math.max(take,notTake);
	}
}

Obsidian Notes

Explorer