Ищите конкретный c комбинированный алгоритм для решения проблемы

Question

Допустим, у меня есть общая сумма покупок, и у меня есть CSV-файл, полный покупок, где некоторые из них составляют эту сумму, а некоторые - нет. Есть ли способ поиска в CSV, чтобы найти комбинацию или комбинации покупок, которые составляют эту сумму? Допустим, общая сумма покупки составляет 155 $, а мой CSV-файл содержит покупки [5.00 $, 40.00 $, 7.25 $, $ 100.00, $ 10.00]. Есть ли алгоритм, который скажет мне комбинации покупок, которые делают из общей суммы?

Редактировать: У меня все еще проблемы с предложенным вами решением. Когда я добавляю эту таблицу с pandas во фрагмент кода, который вы указали, он показывает только одно решение, равное 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

Answer 1

Дп решение:

Пусть 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:

• sum: 40 + 7.25
• последний индекс: 2 (7.25 имеет индекс 2 в массиве)
• используемые значения: значения объединения кортежей 7.25, поэтому [40, 7.25]

Цель используя последний индекс, стоит избегать рассмотрения [7.25, 40] и [40, 7.25]. На самом деле они будут одной и той же комбинацией. Поэтому для создания кортежей из старого следует рассматривать только значения, встречающиеся «после» старого массива

. На каждом шаге мы имеем кортежи одинакового размера, каждый из они агрегируют взятые значения, сумму, которую это составляет, и следующие значения, которые следует учитывать, чтобы увеличить его до большего размера

edit: для обработки чисел с плавающей точкой вы можете заменить (v + sum) <= S на abs (v + sum - S) <= 1e-2, чтобы сказать, что решение достигнуто, когда вы <em>очень близки (здесь расстояние произвольно установлено на 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]