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 that can be achieved by cutting the rod and selling it in the market.
import java.util.*;
public class Solution {
public static int cutRod(int price[], int n) {
//intuition
/*
Since, we have to maximize the profit by cutting the rod in different length
let say length of the rod is 5
and the prices for cutting in different lengths are : 2 5 7 8 10
so we will have to keep on picking lengths(we could take a length any
no of times to maximize the profit of selling the rod) until there is no more length is left to be picked from;
This is exactly similar to unbounded knapsack problem:
*/
int dp[][] = new int[n][n+1];
for(int row []: dp) Arrays.fill(row,-1);
return maxProfit(n-1,price,n,dp);
}
public static int maxProfit(int index, int[] price,int target,int dp[][]){
if(index==0){
return (target/(index+1))*price[index];
}
if(dp[index][target]!=-1) return dp[index][target];
int take = 0;
if(target>=index+1){
take = price[index]+maxProfit(index,price,target-(index+1),dp);
}
int dontTake = 0 + maxProfit(index-1,price,target,dp);
return dp[index][target] = Integer.max(take,dontTake);
}
}
Top comments (0)