On the Change Making Problem
Mailing Matter with Stamps
I’ve developed a recent appreciation for stamps thanks to the postal system’s low rates for mailing out large envelopes. I would just print out online shipping labels, but neither the USPS nor PayPal’s multi-order shipping tool let you buy labels for the first-class large envelope rate. And while I could just use the regular package rate with free services (and before you ask, stamps.com, et al. are non-free), I’d be stuck paying a higher rate.
Fortunately for all folks interested in things philatelic, stamps are denominated in a variety of values and purchasable online from the USPS Postal Store. I’ve got a range of stamps valued anywhere from a penny to a $1.50. (It is regrettable that there are no current issues of any stamps valued at $3.50.)
Why making change in the US is different than stamps
Suppose for a moment that you had 12 different postage stamps and wanted to run through all combinations of four stamps that you could put on the front of an envelope. You’d have to make 1365 combinations. If you were to pick any five, that’s 4368 possibilities. Once you hit six, that’s 12,376. (These numbers are given by n choose r for folks that remember their discrete math.) The numbers blow up really fast. Why is this relevant? Can’t you just pick stamps in the same way you make change?
As it turns out, you can’t. Being able to make change by starting with the largest amount first and moving down if there is any remainder is a deliberate currency design. Many countries, the US included, use a 1-2-5 series for denominating currency values. This means that the greedy solution (starting with the biggest value first) for giving change is actually the optimal one.
While the 1-2-5 series has properties that are useful for money, those properties are less useful for mail. The USPS generally issues values of stamps in a way that only require you to use a single stamp for most types of mail such as letters or postcards. Those values are less useful when you want to mail something that’s calculated, like a package or large envelope.
Take for example, mailing a 4.5oz large envelope. Depending on where you’re mailing it, at today’s prices it might cost $1.82. If I were to use the same approach to pick stamps that I’d use for money, then I’d end up with a $1.15 stamp, a 49¢ stamp, a 10¢ stamp, a 5¢ stamp and a 3¢ stamp. That’s five stamps. If I look carefully, then I can get away with only four stamps: $1.00, 70¢, 10¢ and 2¢.
Tools like the one on Fancyham use the same method as picking money, which means that I’d only ever get minimum number of stamps by coincidence. So how do I find smaller sets of stamps that still work?
Depth-first Non-Greedy Search
As it turns out, solving that is known as the Change-making problem. On first blush, it sounds pretty easy. I started off with some Python that looked like this, courtesy of this stack overflow thread:
1
2
3
4
5
6
7
8
9
10
11
12
13
def minimum_coins(coin_list, offset, target_value):
if target_value == 0:
return 0
elif i == -1 or target_value < 0:
return float('inf')
else:
return min(
minimum_coins(coin_list, offset-1, target_value),
1 + minimum_coins(coin_list, offset, target_value - coin_list[offset])
)
def minimum_change(coin_list, target_value):
return minimum_coins(len(coin_list) - 1, target_value)
This approach worked pretty well for small values of the target value and lists of coins, but I got about 20 minutes into a run with my list of stamps before I gave up on waiting. The problem here is that this code is doing a depth-first search and makes no attempt to cull out paths that it has already visited.
Breadth-first Non-Greedy Search
I was reading about using dynamic programming approach to solve the problem here, but I wasn’t really a fan of building a table for every possible value up to the amount that I want to find. The code there is pretty fast and did solve my problem, but it wasn’t satisfying.
The call-tree graphic on the page got me thinking that this would be a pretty easy breadth-first search to do. The great thing about the breadth-first search is that once I’ve found a level with a solution and explored all of that level, I’m guaranteed to one or more optimal answers.
The general idea is that we start off from the top of a tree with the end value (in this case, 182 cents) and dynamically create nodes that subtract from that value for each level. Once we hit zero, we know we’ve found a valid combination of stamps. So on the first level, we’d expect to see something like this:
1
2
3
4
5
6
7
8
9
10
11
12
{'target': 181, 'combo': [1]}
{'target': 180, 'combo': [2]}
{'target': 179, 'combo': [3]}
{'target': 178, 'combo': [4]}
{'target': 177, 'combo': [5]}
{'target': 172, 'combo': [10]}
{'target': 161, 'combo': [21]}
{'target': 148, 'combo': [34]}
{'target': 133, 'combo': [49]}
{'target': 112, 'combo': [70]}
{'target': 82, 'combo': [100]}
{'target': 67, 'combo': [115]}
We then iterate through those combinations until we get somewhere interesting (or don’t find anything):
1
2
3
4
5
6
7
8
9
10
{'target': 178, 'combo': [1, 1, 1, 1]}
{'target': 177, 'combo': [1, 1, 1, 2]}
{'target': 176, 'combo': [1, 1, 1, 3]}
{'target': 175, 'combo': [1, 1, 1, 4]}
{'target': 174, 'combo': [1, 1, 1, 5]}
{'target': 169, 'combo': [1, 1, 1, 10]}
{'target': 158, 'combo': [1, 1, 1, 21]}
{'target': 145, 'combo': [1, 1, 1, 34]}
...
{'target': 0, 'combo': [2, 10, 70, 100]}
What’s that code look like?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from sets import Set
def search(coin_list, target_value, combo=[]):
# Make sure the list is unique and sorted
coins = list(set(coin_list))
coins.sort()
# Generate a key from each combination and store
# here to avoid revisiting combinations that have
# already been seen.
seencombos = set()
# Let the initial maximum level be infinity for
# ease of comparison.
maxlevel = float('inf')
# Once we've found the max level, squirrel away
# every solution that we find into here.
solutions = []
# Use a list like a queue for keeping track of what to explore.
next_items = []
# Initially seed
for coin in coins:
newcombo = list(combo)
newcombo.append(coin)
next_items.append({
'combo': newcombo,
'target': target_value - coin
})
# Look for solutions while we still have things to explore
while (next_items):
# Grab an item to examine
item = next_items.pop(0)
# We've exceeded the level at which we'll accept solutions, so
# go ahead and return all the valid ones.
if (len(item['combo']) > maxlevel):
return solutions
# Did the item hit the target value? We've found the optimal level!
if (item['target'] == 0):
# Make a note of the depth in which we found the solution
depth = len(item['combo'])
if maxlevel > depth:
maxlevel = depth
# Record this as a valid solution
solutions.append(item)
# Looks like there's still more to go.
# Don't bother with items that that overshot the target
elif (item['target'] > 0):
# Add more combos to explore
for coin in coins:
newcombo = list(item['combo'])
newcombo.append(coin)
newcombo.sort()
# Build a key like "34-49-49" for checking
# if we've seen this combination
combokey = '-'.join(str(val) for val in newcombo)
# Make sure we haven't seen this grouping before adding
if combokey not in seencombos:
seencombos.add(combokey)
next_items.append({
'combo': newcombo,
'target': item['target'] - coin
})
def find_minimum_match(coin_list, target_value):
current_target = target_value
while(True):
result = search(coin_list, current_target)
if result is None:
current_target = current_target + 1
else:
return result
print find_minimum_match(
[115, 100, 70, 49, 34, 21, 10, 5, 4, 3, 2, 1],
182
)
A run looks like this:
1
2
3
4
[
{'target': 0, 'combo': [2, 10, 70, 100]},
{'target': 0, 'combo': [21, 21, 70, 70]}
]
Which are the two optimal solutions given the stamps that I have on hand. Woohoo!