python-3.x - 寻找特定的组合算法来解决问题

Question

假设我有一个购买总额，并且我有一个 csv 文件，其中包含购买总额，其中一些构成该总额，而另一些则不构成。有没有办法搜索 csv 以找到构成该总数的购买组合或组合？假设购买总额为 155 美元，我的 csv 文件包含购买 [5.00$,40.00$,7.25$,$100.00,$10.00]。有没有一种算法可以告诉我购买总额的组合？

编辑：我仍然无法使用您提供的解决方案。当我将这个带有熊猫的电子表格提供给您提供的代码片段时，它只显示一个等于 110.04$ 的解决方案，当有三个时。就像它在没有找到最终解决方案的情况下提前停止。这是我从终端获得的输出 - [57.25, 15.87, 13.67, 23.25]。输出应为 [10.24,37.49,58.21,4.1] 和 [64.8,45.24] 和 [57.25,15.87,13.67,23.25]

    from collections import namedtuple
import pandas

df = pandas.read_csv('purchases.csv',parse_dates=["Date"])

from collections import namedtuple
values = df["Purchase"].to_list()
S = 110.04
Candidate = namedtuple('Candidate', ['sum', 'lastIndex', 'path'])
tuples = [Candidate(0, -1, [])]

while len(tuples):
  next = []
  for (sum, i, path) in tuples:
    # you may range from i + 1 if you don't want repetitions of the same purchase
    for j in range(i+1, len(values)):
      v = values[j]
      # you may check for strict equality if no purchase is free (0$)
      if v + sum <= S:
        next.append(Candidate(sum = v + sum, lastIndex = j, path = path + [v]))
        if v + sum == S :
          print(path + [v])

  tuples = next

标签： python-3.xpandasalgorithmmath

Answer 1

一个dp解决方案：

让S成为你的目标总和

• 构建所有 1 组合。保留总和小于或等于 S 的那些。每当一个等于 S 时，输出它
• 构建所有 2 组合重用以前的组合。
• 重复

from collections import namedtuple
values = [57.25,15.87,13.67,23.25,64.8,45.24,10.24,37.49,58.21,4.1]
S = 110.04
Candidate = namedtuple('Candidate', ['sum', 'lastIndex', 'path'])
tuples = [Candidate(0, -1, [])]

while len(tuples):
  next = []
  for (sum, i, path) in tuples:
    # you may range from i + 1 if you don't want repetitions of the same purchase
    for j in range(i + 1, len(values)):
      v = values[j]
      # you may check for strict equality if no purchase is free (0$)
      if v + sum <= S:
        next.append(Candidate(sum = v + sum, lastIndex = j, path = path + [v]))
        if abs(v + sum - S) <= 1e-2 :
          print(path + [v])
  tuples = next

---

有关元组结构的更多详细信息：

我们想要做的是用一个新值来扩充一个元组。

假设我们从一个只有一个值的元组开始，比如与 关联的元组40。

• 它的总和是微不足道的40
• 添加的最后一个索引是1（它是数字40本身）
• 使用的值是[40]，因为它是唯一的值。

现在要生成下一个元组，我们将从最后一个索引 ( 1) 迭代到数组的末尾。

所以候选人是7.25, 100.00, 10.00

关联的新元组7.25是：

• 和：40 + 7.25
• 最后一个索引：（2在数组中7.25有索引）2
• 使用的值：元组 union 的值7.25，所以[40, 7.25]

使用最后一个索引的目的是避免考虑[7.25, 40]和[40, 7.25]。实际上它们将是相同的组合因此要从旧的元组生成元组，只考虑在数组中的旧元组“之后”出现的值

因此，在每一步，我们都有相同大小的元组，它们中的每一个都会聚合所取的值、它的总和以及要考虑将其扩大到更大大小的下一个值

编辑：要处理浮点数，您可以将 (v+sum)<=S 替换为 abs(v+sum - S)<=1e-2 表示当您非常接近时可以达到解决方案（此处距离任意设置为 0.01）去解决

edit2：这里的代码与https://repl.it/repls/DrearyWindingHypertalk中的代码相同（确实给出了

[64.8, 45.24]
[57.25, 15.87, 13.67, 23.25]
[10.24, 37.49, 58.21, 4.1]