Maximizing Profit in Ribbon Cutting with Minimized Costs
Given a collection of ribbons, each of which has a certain length and can be sold at a specific price. However, to sell we need to make sure they are of equal length but there’s a cost associated with cutting the ribbons into smaller pieces. The objective is to maximize the total profit by selecting an optimal ribbon length for cutting and making the necessary cuts while minimizing the total cutting cost.
Examples:
Input: lengths = [30, 59, 110], costPerCut = 1, salePrice 10 per unit length
Output: 1913
Explanation: Total uniform ribbons: 3 (all ropes are cut to length 30),Total cuts made: 3 (two cuts of 30 to 59 and one cut of 59 to 110),Total profit = (3 x 30 x 10) – (3 x 1) = 900 – 3 = 897. Therefore, the maximum profit achievable is 897.Input: lengths = [26, 103, 59], costPerCut = 1, salePrice 10 per unit length
Output: 1770
Approach: The problem can be solved using the following approach:
The approach calculates the maximum profit by iterating through possible sale lengths, simulating the cutting and selling of ribbons while considering the cost of cuts, and maximizing the profit based on uniform ribbon pieces obtained and total cuts needed.
Steps to solve the problem:
- Sort the array “lengths” in ascending order.
- Initialize “maxProfit” to 0 to keep track of the maximum profit.
- Iterate through possible sale lengths from 1 to the maximum length in “lengths.”
- For each sale length, initialize “totalUniformRibbons” and “totalCuts” to 0.
- Iterate through each ribbon’s length in “lengths“:
- Calculate how many uniform ribbons of the current sale length can be obtained (pieces).
- Calculate the leftover length after cutting (leftover).
- Update “totalUniformRibbons” by adding “pieces” and “totalCuts” by adding the maximum of (pieces – 1) or 0 (cuts needed for each ribbon).
- If there is any leftover length, increment “totalCuts” by 1 (additional cut to discard the leftover).
- Calculate the total profit for the current sale length using the formula: totalProfit = totalUniformRibbons * saleLength * salePrice – totalCuts * costPerCut.
- Update “maxProfit” by taking the maximum of the current “maxProfit” and “totalProfit.”
- Return “maxProfit” as the result.
Below is the implementation of the approach:
C++
#include <iostream> #include <algorithm> #include <vector> class RibbonCuttingProfit { public : static int maximizeProfit( int costPerCut, int salePrice, std::vector< int >& ribbonLengths) { // Sort the ribbon lengths in ascending order std::sort(ribbonLengths.begin(), ribbonLengths.end()); // Initialize the maximum profit to 0 int maxProfit = 0; // Iterate through possible sale lengths for ( int saleLength = 1; saleLength <= ribbonLengths.back(); saleLength++) { // Initialize variables to track total sellable ribbon and total cuts int totalUniformRibbons = 0; int totalCuts = 0; // Iterate through each ribbon length for ( int length : ribbonLengths) { // Calculate how many uniform ribbons of the current saleLength can be obtained int pieces = length / saleLength; int leftover = length % saleLength; // Update totalUniformRibbons based on pieces and totalCuts based on cuts needed totalUniformRibbons += pieces; // Calculate cuts needed for each ribbon totalCuts += std::max(pieces - 1, 0); // Increment totalCuts if there is any leftover length if (leftover > 0) { // Additional cut to discard leftover totalCuts++; } } // Calculate total profit for the current saleLength and update maxProfit int totalProfit = totalUniformRibbons * saleLength * salePrice - totalCuts * costPerCut; maxProfit = std::max(maxProfit, totalProfit); } // Return the maximum profit return maxProfit; } }; int main() { int salePrice = 10; std::vector< int > ribbonLengths = {26, 103, 59}; int costPerCut = 1; int result = RibbonCuttingProfit::maximizeProfit(costPerCut, salePrice, ribbonLengths); std::cout << result << std::endl; // Output: 1770 return 0; } |
Java
import java.util.Arrays; public class RibbonCuttingProfit { public static int maximizeProfit( int costPerCut, int salePrice, int [] ribbonLengths) { // Sort the ribbon lengths // in ascending order Arrays.sort(ribbonLengths); // Initialize the maximum profit to 0 int maxProfit = 0 ; // Iterate through possible sale lengths for ( int saleLength = 1 ; saleLength <= ribbonLengths[ribbonLengths.length - 1 ]; saleLength++) { // Initialize variables to track // total sellable ribbon and total cuts int totalUniformRibbons = 0 ; int totalCuts = 0 ; // Iterate through each ribbon length for ( int length : ribbonLengths) { // Calculate how many uniform // ribbons of the current // saleLength can be obtained int pieces = length / saleLength; int leftover = length % saleLength; // Update totalUniformRibbons // based on pieces and totalCuts // based on cuts needed totalUniformRibbons += pieces; // Calculate cuts needed // for each ribbon totalCuts += Math.max(pieces - 1 , 0 ); // Increment totalCuts if there // is any leftover length if (leftover > 0 ) { // Additional cut to // discard leftover totalCuts++; } } // Calculate total profit for the // current saleLength and // update maxProfit int totalProfit = totalUniformRibbons * saleLength * salePrice - totalCuts * costPerCut; maxProfit = Math.max(maxProfit, totalProfit); } // Return the maximum profit return maxProfit; } public static void main(String[] args) { int salePrice = 10 ; int [] ribbonLengths = { 26 , 103 , 59 }; int costPerCut = 1 ; int result = maximizeProfit(costPerCut, salePrice, ribbonLengths); System.out.println(result); // Output: 1770 } } |
Python3
# Python code to implement the approach class RibbonCuttingProfit: def maximizeProfit(costPerCut, salePrice, ribbonLengths): # Sort the ribbon lengths # in ascending order ribbonLengths.sort() # Initialize the maximum # profit to 0 maxProfit = 0 # Iterate through possible # sale lengths for saleLength in range ( 1 , ribbonLengths[ - 1 ] + 1 ): # Initialize variables to track # total sellable ribbon and total cuts totalUniformRibbons = 0 totalCuts = 0 # Iterate through each ribbon length for length in ribbonLengths: # Calculate how many uniform ribbons # of the current saleLength can be obtained pieces = length / / saleLength leftover = length % saleLength # Update totalUniformRibbons based on # pieces and totalCuts based on cuts needed totalUniformRibbons + = pieces # Calculate cuts needed for each ribbon totalCuts + = max (pieces - 1 , 0 ) # Increment totalCuts if there # is any leftover length if leftover > 0 : # Additional cut to discard # leftover totalCuts + = 1 # Calculate total profit for the # current saleLength and update # maxProfit totalProfit = totalUniformRibbons * saleLength * \ salePrice - totalCuts * costPerCut maxProfit = max (maxProfit, totalProfit) # Return the maximum profit return maxProfit # Driver code salePrice = 10 ribbonLengths = [ 26 , 103 , 59 ] costPerCut = 1 result = RibbonCuttingProfit.maximizeProfit( costPerCut, salePrice, ribbonLengths) print (result) # Output: 1770 |
C#
using System; public class RibbonCuttingProfit { public static int MaximizeProfit( int costPerCut, int salePrice, int [] ribbonLengths) { // Sort the ribbon lengths in ascending order Array.Sort(ribbonLengths); // Initialize the maximum profit to 0 int maxProfit = 0; // Iterate through possible sale lengths for ( int saleLength = 1; saleLength <= ribbonLengths[ribbonLengths.Length - 1]; saleLength++) { // Initialize variables to track total sellable // ribbon and total cuts int totalUniformRibbons = 0; int totalCuts = 0; // Iterate through each ribbon length foreach ( int length in ribbonLengths) { // Calculate how many uniform ribbons of the // current saleLength can be obtained int pieces = length / saleLength; int leftover = length % saleLength; // Update totalUniformRibbons based on // pieces and totalCuts based on cuts needed totalUniformRibbons += pieces; // Calculate cuts needed for each ribbon totalCuts += Math.Max(pieces - 1, 0); // Increment totalCuts if there is any // leftover length if (leftover > 0) { // Additional cut to discard leftover totalCuts++; } } // Calculate total profit for the current // saleLength and update maxProfit int totalProfit = totalUniformRibbons * saleLength * salePrice - totalCuts * costPerCut; maxProfit = Math.Max(maxProfit, totalProfit); } // Return the maximum profit return maxProfit; } public static void Main( string [] args) { int salePrice = 10; int [] ribbonLengths = { 26, 103, 59 }; int costPerCut = 1; int result = MaximizeProfit(costPerCut, salePrice, ribbonLengths); Console.WriteLine(result); // Output: 1770 } } |
Javascript
class GFG { static maximizeProfit(costPerCut, salePrice, ribbonLengths) { // Sort the ribbon lengths in ascending order ribbonLengths.sort((a, b) => a - b); let maxProfit = 0; // Iterate through possible sale lengths for (let saleLength = 1; saleLength <= ribbonLengths[ribbonLengths.length - 1]; saleLength++) { // Initialize variables to track total sellable ribbon and total cuts let totalUniformRibbons = 0; let totalCuts = 0; for (let length of ribbonLengths) { let pieces = Math.floor(length / saleLength); let leftover = length % saleLength; // Update totalUniformRibbons based on pieces and // totalCuts based on cuts needed totalUniformRibbons += pieces; // Calculate cuts needed for each ribbon totalCuts += Math.max(pieces - 1, 0); if (leftover > 0) { totalCuts++; } } // Calculate total profit for the current saleLength and // update maxProfit let totalProfit = totalUniformRibbons * saleLength * salePrice - totalCuts * costPerCut; maxProfit = Math.max(maxProfit, totalProfit); } // Return the maximum profit return maxProfit; } } // Main program const salePrice = 10; const ribbonLengths = [26, 103, 59]; const costPerCut = 1; const result = GFG.maximizeProfit(costPerCut, salePrice, ribbonLengths); console.log(result); |
1770
Time Complexity: O(max_length * n), where max_length is the maximum length in the lengths array, and n is the number of elements in the array.
Auxiliary Space: O(1)
Contact Us