3
\$\begingroup\$

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?

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.