Solving the most profit algorithm [closed]

Question

I am practicing algorithms for upcoming job interviews and I am having trouble correctly implementing this one. I am trying to also maximize efficiency as well. Here is the problem:

Maximize the profit of your business selling metal rods. If you sell N metal rods of length L, you receive N * L * metal_price. The remaining smaller metal rods will be trashed. To cut metal rods, you need to pay cost_per_cut for every cut. What is the max 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 rod is 6. so we cut 4 pieces of length 6 from 1st rod, and throw piece of length 2 from it. next we cut 17 pieces of length 6 from 2nd rod, and throw away piece of length 1. for the third, we cut 9 pieces of length 6, and throw a piece of length 5. so in total we have made 30 cuts. therefore, 30*6*10 - 30*1 - 1770

Here is my attempt so far:

def  maxProfit( cost_per_cut,  metal_price,  lengths):

     profit =0
     for num in lengths:

I'm just not really sure how to go about doing this. Should I iterate over the numbers and see what the lowest number they're divisible by and use that? Any ideas?

Answer 1

Since the input ranges are quite small, can you not just brute force this

    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);
    }