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:

&lt;?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 &gt; $amount) {
            $sum = $sum - $ele;
            $i++;
            $ele = $c[$i];
            continue;
        }
        $sol[] = $ele;
    }
    return $sol;
}

$amount = 356;
$sol = makeChange($amount);
print_r($sol);
?&gt;


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 &gt; 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.