python - 程序，从 10 中选择最好的

Question

我需要用 python 编写一个程序，从一个数组中选择汽车，这个数组充满了 10 辆汽车的质量。这个想法是它装满了一艘驳船，可以最有效地容纳约 8 吨，并且最小的空间没有被填满。我的想法是，它会改变质量并选择最接近最大重量的质量。但是由于我是算法的新手，所以我不知道该怎么做

Answer 1

这是一个一维装箱问题。这是一个NP问题，没有最优解。但是有一种方法可以用贪心算法解决这个问题。您很可能想在 phpclasses.org (bin-packing) 上尝试我的 bin-packing 求解器。

如果我有一个未加权和无向图并且每个节点都连接到每个节点，那么我有 (n^2-n)/2 对节点和整体 n^2-n 可能性/组合：

1,2,3,4,5,...,64
2,1,X,X,X,...,X
3,X,1,X,X,...,X
4,X,X,1,X,...,X
5,X,X,X,1,...,X
.,X,X,X,X,1,.,X
.,X,X,X,X,X,1,X
64,X,X,X,X,X,X,1 

这不是10辆车一样吗？（45 对汽车和 90 种组合/可能性）。我忘了什么吗？错误在哪里？

Answer 2

我会用动态编程来解决这个练习。您应该能够在 O(m*n) 操作中获得最佳解决方案（n 表示汽车数量，m 表示总质量）。但是，只有当质量都是整数时，这才有效。

一般来说，你有一个二进制线性规划问题。这些通常非常困难（NP完全）。

然而，这两种方式都会导致我认为不是初学者材料的算法。您可能会更好地尝试和错误（如您所建议的那样），或者只是尝试所有可能的组合。

Answer 3

像您在这里遇到的问题类似于经典的旅行推销员问题，它要求推销员以最有效的方式访问城市列表。不同之处在于，可以想象，您可能不需要每辆车都装满驳船，而推销员必须走遍每个城市。但问题是相似的。解决问题的蛮力方法是调查所有可能的汽车组合，从 1 辆汽车到全部 10 辆汽车。我们假设每辆汽车拥有任意数量是有效的（即，如果汽车 2 是福特福克斯，您可能有三个福特Foci）。但是，如果汽车列表是特定汽车的确切列表，这很容易更改，并且您只能使用每辆汽车中的一辆。

现在，这很快开始消耗大量时间。随着汽车数量的增加，汽车可能组合的数量呈几何级数增加，这意味着如果数量小于您的预期，则运行程序将花费更长的时间，然后您的生命就剩下时间了。不过，10 应该是可以管理的（结果证明是超过 700,000 种组合，如果每个项目只能有一个，则为 1024 种）。

首先是定义每辆汽车的重量和驳船可以承载的最大重量。

weights = [1, 2, 1, 3, 1, 2, 2, 4, 1, 2, 2]
capacity = 8

现在我们需要一些方法来找到每个可能的组合。Python 的itertools模块有一个函数可以为我们提供给定长度的每种组合，但我们想要所有长度。所以我们将编写一个从 1 到 10 的循环并调用itertools.combinations_with_replacement每个长度。然后我们可以找出每个组合的总重量，如果它高于我们已经找到的任何重量，但仍在容量范围内，我们会记住它是迄今为止我们找到的最好的。

这里唯一真正的技巧是我们不想要权重的组合——我们想要权重索引的组合，因为最后我们想知道将哪些汽车放在驳船上，而不是它们的重量。所以combinations_with_replacements(range(10), ...)而不是combinations_with_replacements(weights, ...). 在循环中，您将希望得到每辆车的重量，并weights[i]加以总结。

我最初在这里有代码，但因为这是家庭作业，所以把它拿出来了。:-) （它最初并没有这样标记，但我应该知道——我责怪时间变化。）

如果您只想允许每辆车中的一辆，您可以使用itertools.combinations而不是combinations_with_replacement.

一条捷径是可能的，因为您在其他地方提到汽车的重量为 1-2 吨。这意味着您知道您至少需要其中的 4 辆 (4 * 2 = 8)，因此您可以跳过 1-3 辆汽车的所有组合。但是，如果教授更改了您的参数，这将无法很好地概括。