<?php
function getCoins(int $totalAmount, $denominations = [2 ,5, 10]){
$amtPossible = [];
foreach($denominations as $d){
$amtPossible[ $d ]= [1, $d];
for($i = $d + 1; $i <= $totalAmount; ++$i){
if(isset($amtPossible[ $i - $d ])){
if(!isset($amtPossible[ $i ]) || $amtPossible[ $i ][0] > 1 + $amtPossible[ $i - $d ][0]){
$amtPossible[ $i ][0] = 1 + $amtPossible[ $i - $d ][0];
$amtPossible[ $i ][1] = $d;
}
}
}
}
if(!isset($amtPossible[ $totalAmount ])){
throw new \Exception("$totalAmount is not possible with the denominations ". implode(",", $denominations));
}
$coins = [];
while($totalAmount > 0){
$coins[] = $amtPossible[ $totalAmount ][1];
$totalAmount -= $amtPossible[ $totalAmount ][1];
}
return $coins;
}
foreach([10, 11, 21, 23, 31, 3] as $test){
try{
echo $test, " => ", implode(", ", getCoins($test)), PHP_EOL;
}catch(\Exception $e){
echo $e->getMessage(), PHP_EOL;
}
}
- Output for 8.1.0 - 8.1.33, 8.2.0 - 8.2.29, 8.3.0 - 8.3.26, 8.4.1 - 8.4.13
- 10 => 10
11 => 5, 2, 2, 2
21 => 10, 5, 2, 2, 2
23 => 10, 5, 2, 2, 2, 2
31 => 10, 10, 5, 2, 2, 2
3 => 3 is not possible with the denominations 2,5,10
preferences:
67.42 ms | 406 KiB | 5 Q