Python在约束下查找最大值

Question

我正在自学python，但无法为特定问题找到正确的解决方案：

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

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)如果cost[i]>c（如果新物品超出了成本限制，您无论如何都无法购买）
• m(i, c) = max(m(i-1, c), m(i-1, c-cost[i]) + gain[i])如果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以了解其他背包算法解决方案。这件很优雅，但其他的就不那么优雅了

编辑：

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