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?