Making change using the smallest possible number of coins

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:

• dollars (100 cents)

• quarters (25 cents)

• dimes (10 cents)

• nickels (5 cents)

• pennies (1 cent)

This outputs an array of coins:

 $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?

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.

StackExchange Code Review Q#106124, answer score: 4