1
$\begingroup$

I've come up with a greedy algorithm proof for the minimum denominations problem, and I'm curious if someone can verify the correctness of the proof for me. I have simplified the problem by restricting the denomination set to the US Coinage System. Thank you very much in advance.

A Formal Definition of the Problem

Given a set of denominations D = {.01, .05, .10, .25} and a number s, find an optimal solution set of denominations O such that the sum of its denominations is equal to s and given any other set of denominations C with the sum of its denominations equal to s, |O| <= |C|. Note: we assume the set of denominations is the US coinage system because the greedy algorithm will work; however, the greedy algorithm will not always find the optimal solution given any generic denomination system.

Mapping the Denominations

Given the US Coinage system, we have the following statements that are true:

.01 = .01
.05 = .01 + .01 + .01 + .01 + .01
.10 = .05 + .05
.25 = .10 + .10 + .05

This means that all the denominations greater than .01 can be mapped or represented as the sum of lower denominations, which is an important property when proving the correctness of the algorithm.

Designing a Greedy Algorithm for the Problem

Let the variable a (short for accumulator) be the current sum of the denominations of the optimal set O we are seeking, which is initialized to zero. To greedily solve this problem, at each step of the algorithm we can choose the largest denomination D[i] such that a + D[i] < s and add d_i to the set O. That’s the greedy algorithm. Now, we can create some pseudo code for the algorithm to solve the problem.

Proc Min-Denominations(D, s)
    O = {}
    I = |D|
    a = 0

    While a < s and i >= 0
        While a+D[i] <= s
            a = a + D[i]
            O = O U {D[i]}
        End While
        i = i - 1
    End While

    Return O
End Proc

Note: It’s important to note that this algorithm assumes that the set of denominations is sorted.

Proving Min-Denominations Finds the Optimal Solution

To prove the greedy algorithm finds the optimal solution, we will use a method known as an exchange argument, which is a powerful way to think about greedy algorithms in general. The exchange argument works by gradually modifying the optimal set O, such that optimality is preserved at each step and transforming it into the optimal set discovered by the greedy algorithm (Kleinberg & Tardos, 2005).

A nonoptimal property for the problem at hand is what I call a denomination expansion, which is a term created for reasoning about this problem. A nonoptimal set O’ with a denomination expansion has a subset C such that the sum of the denominations in C is equal to a denomination di = c1+c2+...+cq.

A. All sets of change with no denomination expansions have the same number of denominations.

By contradiction, assume that A and B are two sets of change such that there are no denomination expansions and |A| = n and |B| = m and n > m. This means the following:

S = a1 + a2 + … + an = b1 + b2 + … + bm

Since n > m, there must be a denomination bi in B and a subset of A called C where |C|=q such that bi = c1 + c2 + … cq. This is by definition a denomination expansion, which contradicts the assertion that A and B are two sets without any denomination expansions.

B. There is an optimal set of denominations that has no denomination expansions.

B1. If O has a denomination expansion, then there is a subset C of O and a denomination d such that d = c1 + c2 + … + cq.

Consider a denomination expansion in O, by definition of denomination expansion, there is a subset C of O such that d = c1 + c2 + … + cq, which means there are q-1 more denominations than necessary.

Now suppose O has at least one denomination expansion, and let it be defined as in (B1) where d = c1 + c2 + … + cq. Now, let’s exchange the denominations c1, c2, …, cq with the denomination d. After the exchange, we can see there is one less denomination expansion O and no new expansions were created. Therefore we have that

B2. After exchanging the denominations we have a change amount with q-1 less denominations such that |O| = n - (q-1)

B3. The new exchanged set of denominations has no more denominations than O when all denomination expansions are removed.

This proof is similar to (A). By contradiction, assume A has no denomination expansions and O is the optimal set of denominations such that |A| = n and |O| = m and m < n since the optimal set must by definition have the least amount of denominations. Also, assume that a1+a2+...+an = o1 + o2 + … + om = s. This implies there is a subset C of A and a denomination oi in O such that oi = c1 + c2 + … + cq. By definition, there is a denomination expansion in A, which contradicts the assertion that A has no denomination expansions.

The optimality of our greedy algorithm now follows immediately.

C. The change produced by Min-Denominations is the optimal minimum number of denominations.

Statement B proves that an optimal set of change has no denomination expansions, and our greedy algorithm produces a set of denominations with no denomination expansions. Statement A shows that any pair of sets of change with no denomination expansions have the same amount of denominations. Therefore, the change obtained by running our greedy algorithm is optimal.

References

Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson.

EDIT I added the mapping the denominations section to improve clarity of the correctness of the proof.

$\endgroup$
1
  • 1
    $\begingroup$ We don't answer "check my answer"-questions. Please edit the question down to a couple of paragraphs, at most, and have a concrete question that we can answer. $\endgroup$
    – Pål GD
    Dec 5, 2023 at 22:26

2 Answers 2

1
$\begingroup$

I decided to write a python script that generates all the optimal solutions for all the change. You can literally scroll through the solutions and observe there are no denomination expansions. So, my proof is indubitably correct at this point.

If change is 2, then the optimal solution is: [1, 1]
If change is 3, then the optimal solution is: [1, 1, 1]
If change is 4, then the optimal solution is: [1, 1, 1, 1]
If change is 6, then the optimal solution is: [5, 1]
If change is 7, then the optimal solution is: [5, 1, 1]
If change is 8, then the optimal solution is: [5, 1, 1, 1]
If change is 9, then the optimal solution is: [5, 1, 1, 1, 1]
If change is 11, then the optimal solution is: [10, 1]
If change is 12, then the optimal solution is: [10, 1, 1]
If change is 13, then the optimal solution is: [10, 1, 1, 1]
If change is 14, then the optimal solution is: [10, 1, 1, 1, 1]
If change is 15, then the optimal solution is: [10, 5]
If change is 16, then the optimal solution is: [10, 5, 1]
If change is 17, then the optimal solution is: [10, 5, 1, 1]
If change is 18, then the optimal solution is: [10, 5, 1, 1, 1]
If change is 19, then the optimal solution is: [10, 5, 1, 1, 1, 1]
If change is 20, then the optimal solution is: [10, 10]
If change is 21, then the optimal solution is: [10, 10, 1]
If change is 22, then the optimal solution is: [10, 10, 1, 1]
If change is 23, then the optimal solution is: [10, 10, 1, 1, 1]
If change is 24, then the optimal solution is: [10, 10, 1, 1, 1, 1]
If change is 26, then the optimal solution is: [25, 1]
If change is 27, then the optimal solution is: [25, 1, 1]
If change is 28, then the optimal solution is: [25, 1, 1, 1]
If change is 29, then the optimal solution is: [25, 1, 1, 1, 1]
If change is 30, then the optimal solution is: [25, 5]
If change is 31, then the optimal solution is: [25, 5, 1]
If change is 32, then the optimal solution is: [25, 5, 1, 1]
If change is 33, then the optimal solution is: [25, 5, 1, 1, 1]
If change is 34, then the optimal solution is: [25, 5, 1, 1, 1, 1]
If change is 35, then the optimal solution is: [25, 10]
If change is 36, then the optimal solution is: [25, 10, 1]
If change is 37, then the optimal solution is: [25, 10, 1, 1]
If change is 38, then the optimal solution is: [25, 10, 1, 1, 1]
If change is 39, then the optimal solution is: [25, 10, 1, 1, 1, 1]
If change is 40, then the optimal solution is: [25, 10, 5]
If change is 41, then the optimal solution is: [25, 10, 5, 1]
If change is 42, then the optimal solution is: [25, 10, 5, 1, 1]
If change is 43, then the optimal solution is: [25, 10, 5, 1, 1, 1]
If change is 44, then the optimal solution is: [25, 10, 5, 1, 1, 1, 1]
If change is 45, then the optimal solution is: [25, 10, 10]
If change is 46, then the optimal solution is: [25, 10, 10, 1]
If change is 47, then the optimal solution is: [25, 10, 10, 1, 1]
If change is 48, then the optimal solution is: [25, 10, 10, 1, 1, 1]
If change is 49, then the optimal solution is: [25, 10, 10, 1, 1, 1, 1]
If change is 50, then the optimal solution is: [25, 25]
If change is 51, then the optimal solution is: [25, 25, 1]
If change is 52, then the optimal solution is: [25, 25, 1, 1]
If change is 53, then the optimal solution is: [25, 25, 1, 1, 1]
If change is 54, then the optimal solution is: [25, 25, 1, 1, 1, 1]
If change is 55, then the optimal solution is: [25, 25, 5]
If change is 56, then the optimal solution is: [25, 25, 5, 1]
If change is 57, then the optimal solution is: [25, 25, 5, 1, 1]
If change is 58, then the optimal solution is: [25, 25, 5, 1, 1, 1]
If change is 59, then the optimal solution is: [25, 25, 5, 1, 1, 1, 1]
If change is 60, then the optimal solution is: [25, 25, 10]
If change is 61, then the optimal solution is: [25, 25, 10, 1]
If change is 62, then the optimal solution is: [25, 25, 10, 1, 1]
If change is 63, then the optimal solution is: [25, 25, 10, 1, 1, 1]
If change is 64, then the optimal solution is: [25, 25, 10, 1, 1, 1, 1]
If change is 65, then the optimal solution is: [25, 25, 10, 5]
If change is 66, then the optimal solution is: [25, 25, 10, 5, 1]
If change is 67, then the optimal solution is: [25, 25, 10, 5, 1, 1]
If change is 68, then the optimal solution is: [25, 25, 10, 5, 1, 1, 1]
If change is 69, then the optimal solution is: [25, 25, 10, 5, 1, 1, 1, 1]
If change is 70, then the optimal solution is: [25, 25, 10, 10]
If change is 71, then the optimal solution is: [25, 25, 10, 10, 1]
If change is 72, then the optimal solution is: [25, 25, 10, 10, 1, 1]
If change is 73, then the optimal solution is: [25, 25, 10, 10, 1, 1, 1]
If change is 74, then the optimal solution is: [25, 25, 10, 10, 1, 1, 1, 1]
If change is 75, then the optimal solution is: [25, 25, 25]
If change is 76, then the optimal solution is: [25, 25, 25, 1]
If change is 77, then the optimal solution is: [25, 25, 25, 1, 1]
If change is 78, then the optimal solution is: [25, 25, 25, 1, 1, 1]
If change is 79, then the optimal solution is: [25, 25, 25, 1, 1, 1, 1]
If change is 80, then the optimal solution is: [25, 25, 25, 5]
If change is 81, then the optimal solution is: [25, 25, 25, 5, 1]
If change is 82, then the optimal solution is: [25, 25, 25, 5, 1, 1]
If change is 83, then the optimal solution is: [25, 25, 25, 5, 1, 1, 1]
If change is 84, then the optimal solution is: [25, 25, 25, 5, 1, 1, 1, 1]
If change is 85, then the optimal solution is: [25, 25, 25, 10]
If change is 86, then the optimal solution is: [25, 25, 25, 10, 1]
If change is 87, then the optimal solution is: [25, 25, 25, 10, 1, 1]
If change is 88, then the optimal solution is: [25, 25, 25, 10, 1, 1, 1]
If change is 89, then the optimal solution is: [25, 25, 25, 10, 1, 1, 1, 1]
If change is 90, then the optimal solution is: [25, 25, 25, 10, 5]
If change is 91, then the optimal solution is: [25, 25, 25, 10, 5, 1]
If change is 92, then the optimal solution is: [25, 25, 25, 10, 5, 1, 1]
If change is 93, then the optimal solution is: [25, 25, 25, 10, 5, 1, 1, 1]
If change is 94, then the optimal solution is: [25, 25, 25, 10, 5, 1, 1, 1, 1]
If change is 95, then the optimal solution is: [25, 25, 25, 10, 10]
If change is 96, then the optimal solution is: [25, 25, 25, 10, 10, 1]
If change is 97, then the optimal solution is: [25, 25, 25, 10, 10, 1, 1]
If change is 98, then the optimal solution is: [25, 25, 25, 10, 10, 1, 1, 1]
If change is 99, then the optimal solution is: [25, 25, 25, 10, 10, 1, 1, 1, 1]
$\endgroup$
1
$\begingroup$

The greedy algorithm is optimal if it only picks 1c coins. It is optimal if it picks a 5c coin as the highest because the alternative is five 1c. It is optimal if it picks one or two 10c because the alternative is two or four 5c. And it is optimal if it picks 25c coins because the alternative is two 10c and replacing one 5c with 10c.

If you had 1c, 9c and 10c then greedy would be non-optimal for 18c. Would be interesting to find an algorithm that finds whether for a combination of coins greedy is not always optimal.

PS. From a different question: Given a set of coins, to check whether the greedy algorithm is always optimal, you only need to check that the greedy algorithm will use at most two coins for any sum of two coins.

Given coins $c_i$, take every pair $i \le j$, and find the largest k such that $c_k \le c_i + c_j$. If $k \ne j$ and $c_k \ne c_i + c_j$ and there is no coin equal to $c_i + c_j - c_k$ then greedy is not always optimal. It follows that greedy is optimal whenever each coin is at least twice the size of the previous one.

$\endgroup$
5
  • $\begingroup$ Hey gnasher729, yeah, that's why I restricted the problem to the US coinage system. Here's an idea for an algorithm to determine if greedy is not always optimal. Have the dynamic programming algorithm find one solution for a set of denominations and have a greedy programming algorithm find a solution for a set of denominations, and then compare the answers. If they are not equal, then the greedy algorithm doesn't work. :-) $\endgroup$ Dec 5, 2023 at 21:27
  • $\begingroup$ Also, I just wanted to add that the greedy algorithm is optimal for the US coinage system in general. cs.fsu.edu/~lacher/courses/COP4531/notes/greedy.html $\endgroup$ Dec 5, 2023 at 21:50
  • $\begingroup$ Greedy is optimal if for every total sum, there is always an optimal solution that picks the largest coin of size at most the total sum. $\endgroup$
    – Pål GD
    Dec 5, 2023 at 22:23
  • $\begingroup$ For example, 1,6,10 does not work since for 12, the optimal solution cannot use 10. $\endgroup$
    – Pål GD
    Dec 5, 2023 at 22:24
  • $\begingroup$ Pal GD, I already know that the greedy algorithm is not optimal for any generic denominational system. That's why I restricted the problem to the US coinage system. $\endgroup$ Dec 5, 2023 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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