我练了即将到来的面试算法和我无法正确地实现这一点。我想也最大限度地提高效率。这里的问题是：

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:

最大限度地提高您的业务销售金属棒的利润。如果你卖的长度L N金属棒，您会收到N * L * metal_price。其余的小金属棒将被丢弃。为了减少金属棒，你需要支付cost_per_cut每一个切割。什么是最大的利润，你可以做什么呢？

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

样本输入：

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

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

下面是我的尝试至今：

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?

推荐答案

虽然由@JasonL提供的算法，适当地回答了这个问题，但我认为只是因为要素的长度在范围[1,1000]我们不'T有必要从1开始，一路去到1000。

While the algorithm provided by @JasonL, suitably answers the question, but I think just because the length of elements lie in the range [1,1000] we don't have to necessarily start from 1 and go all the way to 1000.

以你的情况，例如：

lengths = [26,103, 59]

理想的情况是，如果在最小的这些数字，即26的103和59的一个因素。我们不会有任何垃圾长度和具有最大的利润。

The ideal situation would be if the smallest of these numbers i.e. 26 is a factor of 103 and 59 as well. We won't have to trash any length and have maximum profit.

因此​​，在你的算法这是你应该做的第一次检查。现在如果最小数目不分割的其他两个数字。只是遍历最多至1。@ user3386109，正确地指出，这是没有必要的，最小的一个是总是包含在内，但最大的一个的应该的是，因为我们在这里利润最大化。

So in your algorithm that's the first check you should do. Now if the smallest number doesn't divide the other two numbers. Just loop through the largest number till 1. As @user3386109, rightly pointed out, it's not necessary that the smallest one is always included, however the largest one should be since we are maximising profit here.

所以，你的情况，[1,1000]如果你只是从[1103]检查，发现这些数字小于或等于26103，59的最大倍数，适当计算的利润。你应该有最大的利润。

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

时，该算法的复杂度 - > O（MAX（长）*尺寸（长度）） ，其中长度是数组 [26103，59] 和 MAX（）是最大的元素该数组和尺寸（）重presents该数组的长度。

Time complexity of this algorithm -> O(max(lengths)*size(lengths)) where lengths is the array [26,103, 59] and max() is the largest element of that array and size() represents the length of that array.

希望它可以让你在正确的方向开始。

Hope it gets you started in the right direction.