<?php function addBills(&$change, $value, $count) // add 'count' bills of 'value' to the 'change' array { $change = array_merge($change, array_fill(0, $count, $value)); } function removeBill(&$change, $value) // remove one bill of 'value' from the 'change' array { $key = array_search($value, $change); if ($key !== false) { unset($change[$key]); } } function getChangeTotal($change) // get the total vlaue of the 'change' array { return array_sum($change); } function findMinimum($bills, $wantedTotal, $change = []) { // without bills there's nothing to do if (count($bills) == 0) { return $change; } // get the next smaller bill $value = array_pop($bills); // how many of those will fit? $count = intdiv($wantedTotal - getChangeTotal($change), $value); if ($count > 0) { // add as many bills as will fit addBills($change, $value, $count); while ($count > 0) { // can we find more change? $change = findMinimum($bills, $wantedTotal, $change); // did we reach the wanted total? if ($wantedTotal == getChangeTotal($change)) { return $change; } else { // we have to use smaller bills $count--; removeBill($change, $value); } } } // try a smaller bill return findMinimum($bills, $wantedTotal, $change); } $bills = [2, 5, 10]; print_r(findMinimum($bills, 23)); /* $change = addBills([2,3], 4, 3); print_r($change); print_r(removeBill($change, 4)); */
You have javascript disabled. You will not be able to edit any code.