Problem

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:

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

Solution

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`

.