DEV Community 👩‍💻👨‍💻

Prashant Mishra
Prashant Mishra

Posted on • Originally published at codingninjas.com

Rod cutting Problem (similar to unbounded knapsack)

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

DEV

Thank you.

 
Thanks for visiting DEV, we’ve worked really hard to cultivate this great community and would love to have you join us. If you’d like to create an account, you can sign up here.