寻找一种特定的组合算法来解决问题 [英] Looking for a specific combination algorithm to solve a problem

问题描述

假设我有一个总购买量，而我有一个完整的csv文件，其中有一些构成了总购买量，而有些则没有.有没有一种方法可以搜索csv以找到构成该购买总额的购买组合?假设购买总额为155美元，而我的csv文件中包含购买金额[5.00 $，40.00 $，7.25 $，$ 100.00，$ 10.00].有没有一种算法可以告诉我购买总额的组合?

Let’s say I have a purchase total and I have a csv file full of purchases where some of them make up that total and some don’t. Is there a way to search the csv to find the combination or combinations of purchases that make up that total ? Let’s say the purchase total is 155$ and my csv file has the purchases [5.00$,40.00$,7.25$,$100.00,$10.00]. Is there an algorithm that will tell me the combinations of the purchases that make of the total ?

我仍然无法解决您提供的解决方案.当我将此带有熊猫的电子表格输入代码段时，您需要提供的解决方案只有三种，即只显示等于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]

I am still having trouble with the solution you provided. When I feed this spreadsheet with pandas into the code snippet you provided it only shows one solution equal to 110.04$ when there are three. It is like it is stopping early without finding the final solutions.This is the output that I have from the terminal - [57.25, 15.87, 13.67, 23.25]. The output should be [10.24,37.49,58.21,4.1] and [64.8,45.24] and [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

推荐答案

一种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

---

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

---

More detail about the tuple structure:

我们想要做的是用新值扩充元组.

What we want to do is to augment a tuple with a new value.

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

Assume we start with some tuple with only one value, say the tuple associated to 40.

• 其总和 40
• 最后添加的索引是 1 (它是数字 40 本身)
• 使用的值为 [40] ，因为它是唯一的值.

• its sum is trivially 40
• the last index added is 1 (it is the number 40 itself)
• the used values is [40], since it is the sole value.

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

Now to generate the next tuples, we will iterate from the last index (1), to the end of the array.

所以候选人是 7.25、100.00、10.00

与 7.25 关联的新元组为:

• 总和: 40 + 7.25
• 最后一个索引: 2 ( 7.25 在数组中具有索引 2 )
• 使用的值:元组联合的值 7.25 ，所以 [40，7.25]

• sum: 40 + 7.25
• last index: 2 (7.25 has index 2 in array)
• used values: values of tuple union 7.25, so [40, 7.25]

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

The purpose of using the last index, is to avoid considering [7.25, 40] and [40, 7.25]. Indeed they would be the same combination So to generate tuples from an old one, only consider values occurring 'after' the old one from the array

因此，在每个步骤中，我们都具有相同大小的元组，每个元组都会汇总所取的值，其总和以及要考虑将其增大为更大大小的下一个值

At every step, we thus have tuples of the same size, each of them aggregates the values taken, the sum it amounts to, and the next values to consider to augment it to a bigger size

要处理浮点，您可以将(v + sum)< = S替换为abs(v + sum-S)< = 1e-2，表示当您非常接近时，解决方案已到(此处距离可任意设置为0.01)进行求解

edit: to handle floats, you may replace (v+sum)<=S by abs(v+sum - S)<=1e-2 to say a solution is reach when you are very close (here distance arbitrarily set to 0.01) to solution

edit2:这里的代码与 https://repl.it/repls/DrearyWindingHypertalk (确实可以提供

edit2: same code here as in https://repl.it/repls/DrearyWindingHypertalk (which does give

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

这篇关于寻找一种特定的组合算法来解决问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！