fork(1) download
copy 
  1. <?php
  2.  
  3. error_reporting(-1);
  4.  
  5. $amount = 240;
  6.  
  7. $bills = array(
  8. 	10 => 10,
  9. 	50 => 10,
  10. 	100 => 10,
  11. 	500 => 10,
  12. );
  13.  
  14. $keysBills = array_keys($bills);
  15.  
  16. $attempts = 0;
  17.  
  18. function countBillsSum($billsCopy) {
  19.  
  20. 	$valuesBillsCopy = array_values($billsCopy);
  21. 	$keysBillsCopy = array_keys($billsCopy);
  22.  
  23. 	for($i = 0; $i < count($billsCopy); $i++) {
  24. 		$result[$i] = $valuesBillsCopy[$i] * $keysBillsCopy[$i];
  25. 	}	
  26. 	$result = array_sum($result);
  27. 	return $result;	
  28. }	
  29.  
  30. function findChange($amount, $keysBills, $bills, $billNumber) {
  31.  
  32. 	$x = null;
  33. 	$debugOffset = str_repeat("  ", 3 - $billNumber);
  34. 	echo "{$debugOffset}enter $billNumber\n";
  35.  
  36. 	global $attempts;
  37.  
  38. 	$currentBill = $keysBills[$billNumber];
  39.  
  40. 	$currentMaxBills = min(floor($amount / $keysBills[$billNumber]), $bills[$currentBill]);
  41.  
  42. 	for ($i = $currentMaxBills; $i >= 0; $i--) {
  43.  
  44. 		$attempts++;
  45. 		$billsCopy = $bills;
  46. 		$billsCopy[$currentBill] = $i;
  47.  
  48. 		$sum = countBillsSum($billsCopy);
  49. 		echo "{$debugOffset}  i=$i, bills ".implode(", ", $billsCopy).", sum=$sum\n";
  50.  
  51. 		if ($billNumber > 0) { 
  52. 			$x = findChange($amount, $keysBills, $billsCopy, $billNumber - 1);
  53. 			if ($x) {
  54. 				return $x;
  55. 			}
  56. 		} elseif (countBillsSum($billsCopy) == $amount) {
  57. 			echo "{$debugOffset}  MATCH ".implode(", ", array_values($billsCopy))." (sum=$sum)\n";
  58. 			$x = implode(", ", array_values($billsCopy));
  59. 			return $x;
  60. 		} 
  61. 	}
  62. }
  63.  
  64. echo findChange($amount, $keysBills, $bills, 3);
  65.  
  66. //echo selectMinimumBillsArray(findChange($amount, $keysBills, $bills, 0, array()));
  67.  
  68. echo "\n".$attempts;
Success #stdin #stdout 0.01s 20568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
enter 3
  i=0, bills 10, 10, 10, 0, sum=1600
  enter 2
    i=2, bills 10, 10, 2, 0, sum=800
    enter 1
      i=4, bills 10, 4, 2, 0, sum=500
      enter 0
        i=10, bills 10, 4, 2, 0, sum=500
        i=9, bills 9, 4, 2, 0, sum=490
        i=8, bills 8, 4, 2, 0, sum=480
        i=7, bills 7, 4, 2, 0, sum=470
        i=6, bills 6, 4, 2, 0, sum=460
        i=5, bills 5, 4, 2, 0, sum=450
        i=4, bills 4, 4, 2, 0, sum=440
        i=3, bills 3, 4, 2, 0, sum=430
        i=2, bills 2, 4, 2, 0, sum=420
        i=1, bills 1, 4, 2, 0, sum=410
        i=0, bills 0, 4, 2, 0, sum=400
      i=3, bills 10, 3, 2, 0, sum=450
      enter 0
        i=10, bills 10, 3, 2, 0, sum=450
        i=9, bills 9, 3, 2, 0, sum=440
        i=8, bills 8, 3, 2, 0, sum=430
        i=7, bills 7, 3, 2, 0, sum=420
        i=6, bills 6, 3, 2, 0, sum=410
        i=5, bills 5, 3, 2, 0, sum=400
        i=4, bills 4, 3, 2, 0, sum=390
        i=3, bills 3, 3, 2, 0, sum=380
        i=2, bills 2, 3, 2, 0, sum=370
        i=1, bills 1, 3, 2, 0, sum=360
        i=0, bills 0, 3, 2, 0, sum=350
      i=2, bills 10, 2, 2, 0, sum=400
      enter 0
        i=10, bills 10, 2, 2, 0, sum=400
        i=9, bills 9, 2, 2, 0, sum=390
        i=8, bills 8, 2, 2, 0, sum=380
        i=7, bills 7, 2, 2, 0, sum=370
        i=6, bills 6, 2, 2, 0, sum=360
        i=5, bills 5, 2, 2, 0, sum=350
        i=4, bills 4, 2, 2, 0, sum=340
        i=3, bills 3, 2, 2, 0, sum=330
        i=2, bills 2, 2, 2, 0, sum=320
        i=1, bills 1, 2, 2, 0, sum=310
        i=0, bills 0, 2, 2, 0, sum=300
      i=1, bills 10, 1, 2, 0, sum=350
      enter 0
        i=10, bills 10, 1, 2, 0, sum=350
        i=9, bills 9, 1, 2, 0, sum=340
        i=8, bills 8, 1, 2, 0, sum=330
        i=7, bills 7, 1, 2, 0, sum=320
        i=6, bills 6, 1, 2, 0, sum=310
        i=5, bills 5, 1, 2, 0, sum=300
        i=4, bills 4, 1, 2, 0, sum=290
        i=3, bills 3, 1, 2, 0, sum=280
        i=2, bills 2, 1, 2, 0, sum=270
        i=1, bills 1, 1, 2, 0, sum=260
        i=0, bills 0, 1, 2, 0, sum=250
      i=0, bills 10, 0, 2, 0, sum=300
      enter 0
        i=10, bills 10, 0, 2, 0, sum=300
        i=9, bills 9, 0, 2, 0, sum=290
        i=8, bills 8, 0, 2, 0, sum=280
        i=7, bills 7, 0, 2, 0, sum=270
        i=6, bills 6, 0, 2, 0, sum=260
        i=5, bills 5, 0, 2, 0, sum=250
        i=4, bills 4, 0, 2, 0, sum=240
        MATCH 4, 0, 2, 0 (sum=240)
4, 0, 2, 0
58
https://ideone.com/lgUPwq
language:
PHP (php 7.3.5)
created:
11 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!