解决最大利润算法

Question

我正在为即将到来的工作面试练习算法，但在正确实现此算法时遇到了困难。我也想尽可能地提高效率。以下是问题：

最大化销售金属棒的利润。如果您出售长度为L的N个金属棒，则会收到N * L * metal_price的报酬。剩余的较小金属棒将被丢弃。要切割金属棒，您需要支付cost_per_cut的费用。你能赚到的最大利润是多少？

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

样例输入：

cost_per_cut =1

metal_price =10

lengths = [26,103, 59]

return: 1770

这本书的解决方法是最优长度为6。因此我们从第一根棒子上切割出4块长度为6的杆子，并扔掉长度为2的那一块。接下来，我们从第二根棒子上切割出17块长度为6的杆子，并扔掉长度为1的那一块。对于第三根棒子，我们切割出9块长度为6的杆子，并扔掉长度为5的那一块。所以总共我们做了30次切割。因此，30 * 6 * 10 - 30 * 1 - 1770。

def  maxProfit( cost_per_cut,  metal_price,  lengths):

     profit =0
     for num in lengths:

我不太确定该如何做。我应该遍历这些数字并找到它们可被哪个最小数整除，然后使用它吗？有什么建议吗？

- Mdjon26

---

只是好奇，我们最终是否必须确保销售的杆子有一个最佳长度？就像在这种情况下，所有元素的长度都是6一样？还是我们只关心最大化利润？因为那样我们可以销售不同长度的杆子。 - Vivek Pradhan

Answer 1

由于输入范围非常小，您是否可以直接使用暴力方法解决此问题？

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

- Jason L

---

这是错误的解决方案，在foreach循环中，你需要检查每个长度的利润是否大于0。有可能切割非常昂贵，你不希望对某些长度进行切割。 - enzhou.liu

Answer 2

虽然@JasonL提供的算法可以适当地回答问题，但我认为仅仅因为元素的长度在[1,1000]范围内，我们并不一定要从1开始一直到1000。以你的情况为例：

lengths = [26,103, 59]

理想情况下，最小的数字即26是103和59的因子，这样我们就不必丢弃任何长度并获得最大利润。因此，在您的算法中，这是您应该执行的第一个检查。现在，如果最小的数字不能被另外两个数字整除，只需循环遍历最大的数字直到1。正如@user3386109所指出的那样，最小的数字并不总是包括在内，但最大的数字应该包括在内，因为我们在这里最大化利润。因此，在您的情况下，如果您只从[1,103]中检查，并找到小于或等于26、103、59的这些数字的最大倍数，然后适当地计算利润，您应该会获得最大的利润。该算法的时间复杂度为O(max(lengths)*size(lengths))，其中lengths是数组[26,103,59]，max()是该数组的最大元素，size()表示该数组的长度。希望这能让您朝着正确的方向开始。

- Vivek Pradhan

---

假定最短的木棍将被使用，但这并不总是如此。例如，给定长度[3，59，104]，最大利润处于长度8。这意味着最短的木棍根本没有被使用。当然，您可以将搜索范围限制在最长木棒的长度上。 - user3386109

@user3386109，那很有道理！我会更新我的答案以反映相同的内容。 - Vivek Pradhan