Looking For A Specific Combination Algorithm To Solve A Problem

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 com

Solution 1:

A dp solution:

Let S be your goal sum

• Build all 1-combinations. Keep those which sums less or equal than S. Whenever one equals S, output it
• Build all 2-combinations reusing the previous ones.
• Repeat

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, [])]

whilelen(tuples):
  next = []
  for (sum, i, path) in tuples:
    # you may range from i + 1 if you don't want repetitions of the same purchasefor j inrange(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]))
        ifabs(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.

Assume we start with some tuple with only one value, say the tuple associated to 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.

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

So candidates are 7.25, 100.00, 10.00

The new tuple associated to 7.25 is:

• 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]

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

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: 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]