Making change using the smallest possible number of coins

Question

I have written code based on the Greedy Algorithm. The example can be found here.

Problem: Make a change of a given amount using the smallest possible number of coins.

Coins available are:

1. dollars (100 cents)
2. quarters (25 cents)
3. dimes (10 cents)
4. nickels (5 cents)
5. pennies (1 cent)

This outputs an array of coins:

<?php
function makeChange($amount) {
 $c = array(100, 25, 10, 5, 1);
 $sol = array();
 $sum = 0;
 $i = 0;
 $ele = $c['0'];
 while ($sum != $amount) {
 $sum = $sum + $ele;
 if ($sum > $amount) {
 $sum = $sum - $ele;
 $i++;
 $ele = $c[$i];
 continue;
 }
 $sol[] = $ele;
 }
 return $sol;
}
$amount = 356;
$sol = makeChange($amount);
print_r($sol);
?>

Can this become more optimized?

• Mathieu Guindon: Did you test it? If your code doesn't work as intended, it's not ready for a peer review.
• PHP Learner: Why so many down votes? It really discourages the OP. However I have updated my question.
• Jamal: Since you say it's correct, you can revise the questions to no longer ask about correctness. The update statement can also be removed along with that.

Answer 1

The following is a bit of variation, exploiting that one does not need to subtract the same coin value one-by-one.

$c = array(100, 25, 10, 5, 1); // $coins
$n = array( 0, 0, 0, 0, 0); // Number of coins.
$i = 0;
while ($amount > 0) {
 $k = floor($amount / $c[$i]); // How many coins
 $n[$i] = $k;
 $amount -= $k * $c[$i];
 // Or shorter: $amount %= $c[$i];
 ++$i;
}

Also, I subtract from the original amount instead of adding to $sum.