我正在为即将到来的工作面试练习算法,但在正确实现此算法时遇到了困难。我也想尽可能地提高效率。以下是问题:
最大化销售金属棒的利润。如果您出售长度为L的N个金属棒,则会收到N * L * metal_price的报酬。剩余的较小金属棒将被丢弃。要切割金属棒,您需要支付cost_per_cut的费用。你能赚到的最大利润是多少?
这本书的解决方法是最优长度为6。因此我们从第一根棒子上切割出4块长度为6的杆子,并扔掉长度为2的那一块。接下来,我们从第二根棒子上切割出17块长度为6的杆子,并扔掉长度为1的那一块。对于第三根棒子,我们切割出9块长度为6的杆子,并扔掉长度为5的那一块。所以总共我们做了30次切割。因此,30 * 6 * 10 - 30 * 1 - 1770。
最大化销售金属棒的利润。如果您出售长度为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:
我不太确定该如何做。我应该遍历这些数字并找到它们可被哪个最小数整除,然后使用它吗?有什么建议吗?