# Real-world set theory/combinatorics problem

I have a real-world problem, and, unfortunately, being an engineer, I feel compelled to solve it.

I went to Walmart the other day and attempted to purchase eleven over-the-counter (OTC) health-related products totaling $104.07. At checkout,$$61.54 of the total was approved for payment by my insurance OTC benefit card, while$42.53 of the total was not approved (which I paid for in cash.)

The receipt does NOT indicate which items were approved and which were not.

The problem I'm trying to solve is: Which items were approved and which were not?

The eleven items and their costs are as follows:

• Gauze pads 2.34
• Alcohol 3.48
• Antibiotic cream 4.12
• Lidocaine cream 4.94
• Bandages 4.97
• Hydrocortisone 7.12
• Peptobismol 8.56
• Toothpaste 10.59
• Melatonin 13.76
• Ibuprofan 19.71

In summary: There are eleven elements in total divided into two sets.

Set "A" contains "n" elements totaling $61.54. Set "B" contains "11-n" elements totaling$42.53.

What are the "n" elements contained in set "A"?

I don't have a clue as to how to go about solving this.

I do realize, however, that there may be more than one solution to this problem.

Edit: Taxes have been removed from the totals.

• This seems like the knapsack problem, which is NP complete. Of course, in this case, you can just try all $2^{10}$ partitions (reduced from $2^{11}$ because you don't care which of the two parts an item ends up in). Jun 28 at 17:18
• More specifically, the subset sum problem. Jun 28 at 17:20
• Um..., I substituted Ibuprofen as the name for a more personal item... Jun 28 at 17:35
• Not really - there are people here who dislike such answers. But I simply tried all $2048$ possibilities Jun 28 at 17:39
• @JohnE Given the nature of your question, I'm perfectly willing to tell you my answer: it's the gauze, the alcohol, the bandages, the hydrocortisone, the peptobismol, the toothpaste, and the loratadine. My implementation for the solution can be found here if you'd like to take a look, I think it's a bit better than just generating all possible gatherings of elements, but in the grand scheme of things probably not by much Jun 28 at 17:47

Set A = 61.54 = [('Gauze pads', 2.34), ('Alcohol', 3.48), ('Bandages', 4.97), ('Hydrocortisone', 7.12), ('Peptobismol', 8.56), ('Toothpaste', 10.59), ('Loratadine', 24.48)]

But I cheated...

#!/usr/bin/env python

from __future__ import print_function

sumA = 61.54
sumB = 42.53

thing = (("Gauze pads", 2.34),
("Alcohol", 3.48),
("Antibiotic cream", 4.12),
("Lidocaine cream", 4.94),
("Bandages", 4.97),
("Hydrocortisone", 7.12),
("Peptobismol", 8.56),
("Toothpaste", 10.59),
("Melatonin", 13.76),
("Ibuprofen", 19.71),
)

def subset (thing, k):
# Return k-th subset and its complement.
s0, s1 = [], []
for t in thing:
if k % 2 == 0:
s0.append (t)
else:
s1.append (t)
k //= 2
return s0, s1

def subsum (s):
# Sum the costs.
return sum (e[1] for e in s)

def equals (a, b):
# Needed due to IEEE-754 floating-point quirks.
return abs(a - b) < 1e-8

sumAB = subsum (thing)

if not equals (sumAB, sumA + sumB):
print ("No solution")
else:
for k in range (2 ** len(thing)):
s0, _ = subset (thing, k)
if equals (subsum(s0), sumA):
print ("Set A = %.2f =" % sumA, s0)