python - 求解最大利润算法

<分区>

我正在为即将到来的工作面试练习算法，但我无法正确实现这个算法。我也在努力最大限度地提高效率。这是问题所在:

最大限度地提高您销售金属棒的业务的利润。如果您出售 N 根长度为 L 的金属棒，您将收到 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:

我只是不太确定该怎么做。我是否应该遍历数字并查看它们可被整除的最小数字并使用它？有什么想法吗？

最佳答案

由于输入范围很小，你能不能不暴力破解这个

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

关于python - 求解最大利润算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27030757/

上一篇：python - SQLAlchemy，以惯用的 Python 方式隔离和重试可序列化的事务

下一篇：Python 多处理队列比 pool.map 慢

相关文章：

python - 如何检查嵌套列表是否有值

java - DFS over string trie (前缀)

c# - 数组中等于 N 的 K 个元素之和

algorithm - F# 从列表中插入/删除项目

excel - VBA 使用递归而不是循环

python - 使用 cronjob 运行带有参数的 python 脚本会出现错误 :/bin/sh: password: command not found

python - 信用计算器产生错误的输出

python - Azure 应用服务上的 Flask 应用程序抛出 "405 Method Not Allowed"错误

Python:逻辑回归 max_iter 参数降低了准确性

algorithm - 如何检查依赖图中的额外冲突信息？