Largest Profit Algorithm Solution

Question

I use algorithms for upcoming job interviews, and I'm having trouble correctly implementing this. I also try to increase efficiency. Here is the problem:

Maximize the profit of your business by selling metal rods. If you sell metal rods of length L, you get N * L * metal_price. The remaining smaller metal rods will be destroyed. To cut metal rods, you need to pay cost_per_cut for each cut. What is the maximum profit you can make?

constraints: lengths will be 1 to 50 elements, inclusive. each element of length will lie in range [1,10000] 1 <= metal_price, cost_per_cut <=1000 

sample input:

 cost_per_cut =1 metal_price =10 lengths = [26,103, 59] return: 1770 

how the book solved this is that the most optimal length of the bar is 6., so we cut 4 parts of length 6 from the 1st bar and push a piece of length 2 out of it. then we cut 17 pieces of length 6 from the 2nd rod and throw out a piece of length 1. For the third, we cut 9 pieces of length 6 and throw a piece of length 5, so in the end we made 30 cuts. therefore 30 * 6 * 10 - 30 * 1 - 1770

Here is my attempt:

 def maxProfit( cost_per_cut, metal_price, lengths): profit =0 for num in lengths: 

I'm just not sure how to do this. Should I iterate over the numbers and see what is the lowest number they divide and use? Any ideas?

Answer 1

Since the input ranges are pretty small, can't you just translate that value

  static int getProfit(int[] rods, int cutCost, int metalPrice, int L) { int profit = 0; foreach (int rod in rods) { if (rod % L == 0) { profit += (metalPrice * rod - (rod / L - 1) * cutCost); } else { profit += (metalPrice * (rod - rod % L) - (rod / L) * cutCost); } } return profit; } static void Main(string[] args) { int[] rods = new int[] { 26,103,59}; int cutCost =1; int metalPrice=10; int maxProfit = 0; for (int L = 1; L <= 10000; ++L) { int profit= getProfit(rods, cutCost, metalPrice, L); if (profit > maxProfit) { maxProfit = profit; } } Console.WriteLine(maxProfit); } 

Answer 2

While the algorithm provided by @JasonL is suitable for answering the question, but I think that only because the length of the elements lies in the range [1,1000], we do not have to start from 1 and go all the way to 1000.

Take your example, for example:

 lengths = [26,103, 59] 

An ideal situation would be if the smallest of these numbers, i.e. 26 is also a factor of 103 and 59. We do not have to spend any length and get the maximum profit.

So, in your algorithm you have to do the first check. Now, if the smallest number does not divide the other two numbers. Just scroll the highest number to 1. As user user user user user user user user user user user user user user user user user user user user user user user user user user user user Categories Domain Names E-Marketing Cars Self Portrait Pregnancy Improvement and Delivery Business Blogs Web Design Webmasters Web

So, in your case, instead of checking with [1,1000], if you just check with [1,103] and find the largest multiple of these numbers less than or equal to 26,103, 59, and calculate the profit accordingly. You should have maximum profit.

The time complexity of this algorithm is → O(max(lengths)*size(lengths)) , where lengths is an array [26,103, 59] , and max() is the largest element of this array, and size() is the length of this array.

Hope you start in the right direction.