Maximum Coin Partition

Question

Since standing at the point of sale in the supermarket yesterday, once more trying to heuristically find an optimal partition of my coins while trying to ignore the impatient and nervous queue behind me, I've been pondering about the underlying algorithmic problem:

Given a coin system with values v₁,...,v_n, a limited stock of coins a₁,...,a_n and the sum s which we need to pay. We're looking for an algorithm to calculate a partition x₁,...,x_n (with 0<=x_i<=a_i) with x₁*v₁+x₂*v₂+...+x_n*v_n >= s such that the sum x₁+...+x_n - R(r) is maximized, where r is the change, i.e. r = x₁*v₁+x₂*v₂+...+x_n*v_n - s and R(r) is the number of coins returned from the cashier. We assume that the cashier has an unlimited amount of all coins and always gives back the minimal number of coins (by for example using the greedy-algorithm explained in SCHOENING et al.). We also need to make sure that there's no money changing, so that the best solution is NOT to simply give all of the money (because the solution would always be optimal in that case).

Thanks for your creative input!

Answer 1

If I understand correctly, this is basically a variant of subset sum. If we assume you have 1 of each coin (a[i] = 1 for each i), then you would solve it like this:

sum[0] = true
for i = 1 to n do
    for j = maxSum downto v[i] do
        sum[j] |= sum[j - v[i]]

Then find the first k >= s and sum[k] is true. You can get the actual coins used by keeping track of which coin contributed to each sum[j]. The closest you can get your sum to s using your coins, the less the change will be, which is what you're after.

Now you don't have 1 of each coin i, you have a[i] of each coin i. I suggest this:

sum[0] = true
for i = 1 to n do
    for j = maxSum downto v[i] do
       for k = 1 to a[i] do
           if j - k*v[i] >= 0 do
               sum[j] |= sum[j - k*v[i]] <- use coin i k times

It should be fairly easy to get your x vector from this. Let me know if you need any more details.