# 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:

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?

• Did you test it? If your code doesn't work as intended, it's not ready for a peer review. – Mathieu Guindon Sep 30 '15 at 13:18
• Why so many down votes? It really discourages the OP. However I have updated my question. – PHP Learner Oct 1 '15 at 4:51
• 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. – Jamal Oct 1 '15 at 4:55

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