3
$\begingroup$

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
  • Loratadine 24.48

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.

$\endgroup$
13
  • 2
    $\begingroup$ 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). $\endgroup$
    – Brian Tung
    Jun 28 at 17:18
  • 3
    $\begingroup$ More specifically, the subset sum problem. $\endgroup$
    – peterwhy
    Jun 28 at 17:20
  • 1
    $\begingroup$ Um..., I substituted Ibuprofen as the name for a more personal item... $\endgroup$
    – John E
    Jun 28 at 17:35
  • 1
    $\begingroup$ Not really - there are people here who dislike such answers. But I simply tried all $2048$ possibilities $\endgroup$
    – Henry
    Jun 28 at 17:39
  • 2
    $\begingroup$ @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 $\endgroup$
    – Stephen Donovan
    Jun 28 at 17:47

1 Answer 1

Reset to default
4
$\begingroup$

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),
         ("Loratadine", 24.48)
)

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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.