fork download
copy 
  1. <?php
  2.  
  3.  
  4. header('Content-Type: text/plain; charset=UTF-8');
  5.  
  6. $amount = 1600;
  7.  
  8. $bills = array(
  9.     5000    => 2,
  10.     2000    => 1,
  11.     1000    => 1,
  12.     500     => 1,
  13.     200     => 4,
  14.     100     => 0
  15. );
  16.  
  17. function foo ($amount, $bills, $billUsed=NULL, $result=NULL)
  18. {
  19.  
  20.     $paid = 0;
  21.     $remain = $amount;
  22.     $k = 0;
  23.     $billKeys = array();
  24.  
  25.     foreach ($bills as $billValue => $billAmount) {
  26.  
  27.         if ($billValue > $amount || $billAmount == 0 || (isset($billUsed[$billValue]) && $billUsed[$billValue] == TRUE)) {
  28.             continue;
  29.         }
  30.  
  31.         $billPaymentAmount = floor($remain / $billValue);
  32.  
  33.         if ($billPaymentAmount == 0) {
  34.             continue;
  35.         }
  36.  
  37.         if ($billPaymentAmount > $billAmount) {
  38.             $billPaymentAmount = $billAmount;
  39.         }
  40.  
  41.         $remain -= $billPaymentAmount * $billValue;
  42.  
  43.         $billUsed[$billValue] = TRUE;
  44.         $billKeys[] = $billValue;
  45.         $k++;
  46.  
  47.         $result[] = "$billPaymentAmount x $billValue";
  48.  
  49.     }
  50.  
  51.     if ($remain != 0) {
  52.         array_pop($result);
  53.         $l = $k - 1;
  54.         $remain += $billKeys[$l];
  55.         foo($remain, $bills, $billUsed, $result);
  56.     }
  57.  
  58. var_dump($result);
  59. }
  60.  
  61. foo($amount, $bills);
Success #stdin #stdout 0.01s 20568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
array(2) {
  [0]=>
  string(8) "1 x 1000"
  [1]=>
  string(7) "3 x 200"
}
array(1) {
  [0]=>
  string(8) "1 x 1000"
}
https://ideone.com/0Uds1T
language:
PHP (php 7.3.5)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!