Python 在约束条件下求最大值

Question

我正在自学 python，但我找不到针对特定问题的正确解决方案：

我得到 x $。我可以购买不同物品的清单，每个物品都有一定的价格（成本）并提供特定的收益（收益）我想获得 x $ 的最大收益。每个项目只有 1 个。让我们说：

dollars = 10
cost = [5, 4, 1, 10]
gain = [7, 6, 4, 12]

此处 => 最大增益为 17

使用基于排列的天真的解决方案，我设法在项目数量较少时找到解决方案。但是当项目数量增加时，时间增加并且计算机崩溃。

有解决那种pb的典型算法吗？

Answer 1

您在其中一条评论中提到对解决方案的代码不感兴趣，所以我将只解释算法。这个问题更广为人知的是 0-1 knapsack problem。解决它的典型方法是使用 dynamic programming:

让我们定义一个我们称之为 m(i, c) 的值，这是您花费最多 c 美元并且只购买前 i 中的商品可以获得的最大收益你的名单。你有：
m(0, c) = 0（如果你不能购买任何物品，你将不会获得任何收益）。
m(i, c) = m(i-1, c) if cost[i]>c（如果新商品超过成本限制，你无论如何都买不到）
m(i, c) = max(m(i-1, c), m(i-1, c-cost[i]) + gain[i]) if cost[i]<=c（你现在可以购买物品 i。你要么买，要么不买，你能得到的最大收益其中是这两个选项中的最大值）

要获得最优惠的价格，您只需计算 m(len(cost), dollars)。例如，您可以使用 for 循环来执行此操作，在该循环中，您将通过填充 m 值列表为每个 i 计算 len(cost) m(i, dollars) .要弄清楚实际购买了哪些物品，而不仅仅是最大收益，您必须在填写 m.

时将它们保存在单独的列表中

Answer 2

这听起来像是一道 LeetCode 题，但我会给你一个不错的答案（不是最好的，绝对可以优化）：

问题

假设您正在尝试从不重复任何项目的任何 n 个项目中找出最大收益，以下算法可能有效。

解决方案

您将采用压缩成本和收益的最高比率，并从压缩变量中删除该索引。然后，你会重做这个问题，直到你没有足够的钱来购买：

代码：

#!/usr/bin/env python3
dollars = 10
cost = [5, 4, 1, 10]
gain = [7, 6, 4, 12]

result_gain = 0

zipped = [i for i in zip(cost, gain)]
largestgain = []

# create ratio of cost to gain and pick from the smallest to the largest
ratios = []
for x in zipped:
    # divide the gain by the cost
    ratios.append(x[1]/x[0])

# create a largest variable to grab the largest ratio from a for loop for every updated index
largest = 0
for x in range(0, len(zipped)):
    for index, ratio in enumerate(ratios):
        if index == 0:
            largest = ratio
        else:
            if ratio > largest:
                largest = ratio # let largest be the new largest ratio

    # get the index of the largest ratio
    largest = ratios.index(largest)
    print(largest)

    # append the largest gain to a list of what should be added up later
    largestgain.append(zipped[largest])

    # check if dollars, when subtracted from the first index, yield less than 0
    if dollars - zipped[largest][0] < 0:
        break
    # if not, subtract dollars from total and update resulted gain
    else:
        dollars = dollars - zipped[largest][0]
        result_gain = result_gain + zipped[largest][1]

    # delete the largest zipped variable in order to redo this process
    del zipped[largest]
    # delete the largest ratio as well in order to redo this process
    del ratios[largest]

    # print the list that would yield you the largest ratios in order from largest to smallest, but in the form of a zipped list
    print(largestgain)

# The max amount of gain earned
print(result_gain)

解释：

我添加了 shebang 以便您可以自己测试它，但它应该可以完美运行。我已经评论了我的代码，以便您可以阅读算法的过程。如果需要，可以使用更大的列表进行测试。

请注意，成本和增益列表的长度没有异常检查器，因此如果成本列表大于增益列表，它将划分一个不存在的缓冲区，并且会出现异常抛出。

如果此算法太慢，请随时检查此 resource 以了解其他背包算法解决方案。这个很优雅，但其他的，没那么多。

编辑：

正如评论者所指出的，这是一个非常贪婪的算法，并不适用于所有值。参考理论以获得更好的解释。

Python 在约束条件下求最大值

Python find max under constraint

python

algorithm

optimization

knapsack-problem

问题

解决方案

代码：

解释：

编辑：