Reputation: 373
I was recently posed the following interview question to be answered in Python - given a list of quantity-value pairs, find the optimal combination(s) of sets of values whose sum is as close to, and at least as large as, some provided value.
For example, given: [(1, $5), (3, $10), (2, $15)], and a desired value of $36, the answer would be [(2,$15), (1,$10)] or [(1,$15), (2,$10), (1,$5)]. The reason is that $40 is the least sum greater than or equal to $36 that can be achieved, and these are the two ways to achieve that sum.
I got stumped. Does anyone have a solution?
Upvotes: 0
Views: 1309
Reputation: 30288
The numbers are so small you can just brute force it:
In []:
notes = [(1, 5), (3, 10), (2, 15)]
wallet = [n for a, b in notes for n in [b]*a]
combs = {sum(x): x for i in range(1, len(wallet)) for x in it.combinations(wallet, i)}
target = 36
for i in sorted(combs):
if i >= target:
break
i, combs[i]
Out[]:
(40, (5, 10, 10, 15))
You can extend this for all combinations, just replace the combs
dictionary comprehension with:
combs = {}
for i in range(1, len(wallet)):
for x in it.combinations(wallet, i):
combs.setdefault(sum(x), set()).add(x)
...
i, combs[i]
Out[]:
(40, {(5, 10, 10, 15), (10, 15, 15)})
Upvotes: 1