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?

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.