Geek Answers Handbook

Maximum section of coins

Today, when we are standing at a point of sale in a supermarket, once again trying to heuristically find the optimal separation of my coins, trying to ignore the impatient and nervous queue behind me, I thought about the underlying algorithmic problem:

Given a coin system with values ​​v 1 , ..., v n , a limited supply of coins a 1 , ..., a n and the amount s we have to pay. We are looking for an algorithm to calculate the section x 1 , ..., x n (with 0 <= x i <= a i ) with x 1 * v 1 + x 2 * v 2 + ... + x n * v n > = s, so that the sum x 1 + ... + x n - R (r) is maximized, where r is the change, i.e. r = x 1 * v 1 + x2 * v 2 + ... + x n * v n - s and R (r) is the number of coins returned from the cash register. We assume that the cashier has an unlimited number of all coins and always returns the minimum number of coins (for example, using the greedy algorithm described in SCHOENING and others). We also need to make sure that there is no money, so the best solution is not just to give all the money (because the solution will always be optimal in this case).

Thank you for your creative contribution!

+5
source share
1 answer

, . , 1 (a[i] = 1 i), :

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

k >= s sum[k] - true. , , , sum[j]. , s, , , .

1 i, a[i] i. :

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

x . , .

+1

More articles:


All Articles