I recently learned the proof of the greedy algorithm solution to make change problem:

There's a set of coins $\{c_1 < c_2<...<c_{i-1}<c_i\}$. $c_i$ is an integer and $c_{i+1}=q\cdot c_i$ where $q$ is an integer. Given number $x$ what is the least amount of coins needed to pay $x$ of some currency?

The solution will use a greedy algorithm. In order to prove that greedy algorithm is correct we suppose that we have: $$ \{c_1, c_2,...,c_{i-1},c_i\} \quad\text{coins set}\\ k_1, k_2,...,k_{i-1},k_i\quad\text{how many times}\quad c_i \quad\text{is repeated}\\ c_1=1 $$ We also suppose that there's another different algorithm that works and in it there're $p_i$ repetitions of $c_i$.

Then $p_i<k_i$. Then we have some "deficit" on $p_i$ part then the deficit must be resolved by some former combination of $p$ and $c$.

We'll prove that the deficit will never be resolved because:

$$ p_1\cdot c_1<c_2\qquad (1) $$ then: $$ p_1\cdot c_1 \le c_2-c_1 \implies\qquad (2)\\ p_2\cdot c_2 \le c_3-c_2 \implies\\ \vdots\\ p_i\cdot c_i \le c_i-c_{i-1} \implies $$ Now if we sum up the LHS and RHS we get: $$ \sum_{k=1}^{i-1}p_k\cdot c_k\le c_i-c_1<c_i $$ which proves that the deficit is never made up for by $\sum p_k\cdot c_k$.

Two things I can't grasp:

why does $(1)$ and $(2)$ hold?

  • 2
    $\begingroup$ But the greedy algorithm doesn't solve the problem! For example, suppose the coins are $\{1,15,25\}$. Then to make change for $30$, it is best to use $(15,15)$, but the greedy algorithm uses $(25,1,1,1,1,1)$. $\endgroup$ – Théophile Oct 19 '17 at 14:31
  • $\begingroup$ @Théophile this particular algorithm that I described is not always correct I meant some greedy algorithm in general. I'll delete the description of my algorithm. $\endgroup$ – Yos Oct 19 '17 at 14:32
  • $\begingroup$ Hmm. What do you mean by "some greedy algorithm in general"? Which greedy algorithm solves this problem? $\endgroup$ – Théophile Oct 19 '17 at 14:53
  • 1
    $\begingroup$ @Théophile Note the extra condition that $c_{i+1}= qc_{i}$ for integer $q$, which is why your counterexample does not work for this variant. $\endgroup$ – Michael Biro Oct 19 '17 at 14:55
  • $\begingroup$ @MichaelBiro Ah, I see. That condition was added in a later edit. $\endgroup$ – Théophile Oct 19 '17 at 15:13

(1) is true because you could have used $c_2$'s instead if $p_1c_1 \geq c_2$.

(2) is true from (1) because $qc_1 = c_2$ for some integer $q$, so if $p_1c_1 < c_2$ then $(p_1 + 1)c_1 \leq c_2$

  • $\begingroup$ Can I say that because $p_1c_1<c_2$ then $(p_1+1)c_1\le c_2$ because we're dealing with integers and the minimal step is $1$? $\endgroup$ – Yos Oct 19 '17 at 15:16
  • 1
    $\begingroup$ @Yos Since $c_1 = 1$ here, yes. However, the other steps require the same conclusion that $(p_i+1)c_i \leq c_{i+1}$ for all other $c_i$, which won't necessarily be $1$. You want to use the fact that $c_{i+1}$ cannot lie between $p_ic_i$ and $(p_i + 1)c_i$ $\endgroup$ – Michael Biro Oct 19 '17 at 15:18
  • $\begingroup$ So is it because we proved this on $(p_1+1)c_1\le c_2$ that we can also use the proof on $(p_i+1)c_i\le c_{i+1}$? $\endgroup$ – Yos Oct 19 '17 at 15:20
  • 1
    $\begingroup$ @Yos The argument is the same. Since $c_{i+1}$ is a multiple of $c_i$, it cannot lie strictly between two consecutive multiples of $c_i$. $\endgroup$ – Michael Biro Oct 19 '17 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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