fork download
copy 
  1. <?php
  2.  
  3. error_reporting(-1);
  4.  
  5. $amount = 620;
  6.  
  7. $bills = array(
  8. 	10 => 5,
  9. 	50 => 0,
  10. 	200 => 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, $leftAmount) {
  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. 	$leftAmount = $leftAmount - $currentBill*$currentMaxBills;
  42. 	echo "leftAmount=".$leftAmount;
  43.  
  44. 	//echo $amount."\n";
  45. 	//echo floor($amount / $keysBills[$billNumber])."\n";
  46. 	//echo $bills[$currentBill]."\n";
  47.  
  48. 	for ($i = $currentMaxBills; $i >= 0; $i--) {
  49.  
  50. 		$attempts++;
  51. 		$billsCopy = $bills;
  52. 		$billsCopy[$currentBill] = $i;
  53.  
  54. 		$sum = countBillsSum($billsCopy);
  55. 		echo "{$debugOffset}  i=$i, billNumber=$billNumber, bills ".implode(", ", $billsCopy).", sum=$sum\n";
  56.  
  57. 		if ($billNumber > 0) { 
  58. 			$x = findChange($amount, $keysBills, $billsCopy, $billNumber - 1, $leftAmount);
  59. 			if ($x) {
  60. 				return $x;
  61. 			}
  62. 		} 
  63. 		if ($leftAmount == 0) {
  64. 			echo "{$debugOffset}  MATCH ".implode(", ", array_values($billsCopy))." (sum=$sum)\n";
  65. 			$x = implode(", ", array_values($billsCopy));
  66. 			return $x;
  67. 		} 
  68. 	}
  69. }
  70.  
  71. echo findChange($amount, $keysBills, $bills, 3, $amount);
  72. echo "\n".$attempts;
Success #stdin #stdout 0.01s 20568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
enter 3
leftAmount=120  i=1, billNumber=3, bills 5, 0, 10, 1, sum=2550
  enter 2
leftAmount=-480    i=3, billNumber=2, bills 5, 0, 3, 1, sum=1150
    enter 1
leftAmount=-480      i=0, billNumber=1, bills 5, 0, 3, 1, sum=1150
      enter 0
leftAmount=-530        i=5, billNumber=0, bills 5, 0, 3, 1, sum=1150
        i=4, billNumber=0, bills 4, 0, 3, 1, sum=1140
        i=3, billNumber=0, bills 3, 0, 3, 1, sum=1130
        i=2, billNumber=0, bills 2, 0, 3, 1, sum=1120
        i=1, billNumber=0, bills 1, 0, 3, 1, sum=1110
        i=0, billNumber=0, bills 0, 0, 3, 1, sum=1100
    i=2, billNumber=2, bills 5, 0, 2, 1, sum=950
    enter 1
leftAmount=-480      i=0, billNumber=1, bills 5, 0, 2, 1, sum=950
      enter 0
leftAmount=-530        i=5, billNumber=0, bills 5, 0, 2, 1, sum=950
        i=4, billNumber=0, bills 4, 0, 2, 1, sum=940
        i=3, billNumber=0, bills 3, 0, 2, 1, sum=930
        i=2, billNumber=0, bills 2, 0, 2, 1, sum=920
        i=1, billNumber=0, bills 1, 0, 2, 1, sum=910
        i=0, billNumber=0, bills 0, 0, 2, 1, sum=900
    i=1, billNumber=2, bills 5, 0, 1, 1, sum=750
    enter 1
leftAmount=-480      i=0, billNumber=1, bills 5, 0, 1, 1, sum=750
      enter 0
leftAmount=-530        i=5, billNumber=0, bills 5, 0, 1, 1, sum=750
        i=4, billNumber=0, bills 4, 0, 1, 1, sum=740
        i=3, billNumber=0, bills 3, 0, 1, 1, sum=730
        i=2, billNumber=0, bills 2, 0, 1, 1, sum=720
        i=1, billNumber=0, bills 1, 0, 1, 1, sum=710
        i=0, billNumber=0, bills 0, 0, 1, 1, sum=700
    i=0, billNumber=2, bills 5, 0, 0, 1, sum=550
    enter 1
leftAmount=-480      i=0, billNumber=1, bills 5, 0, 0, 1, sum=550
      enter 0
leftAmount=-530        i=5, billNumber=0, bills 5, 0, 0, 1, sum=550
        i=4, billNumber=0, bills 4, 0, 0, 1, sum=540
        i=3, billNumber=0, bills 3, 0, 0, 1, sum=530
        i=2, billNumber=0, bills 2, 0, 0, 1, sum=520
        i=1, billNumber=0, bills 1, 0, 0, 1, sum=510
        i=0, billNumber=0, bills 0, 0, 0, 1, sum=500
  i=0, billNumber=3, bills 5, 0, 10, 0, sum=2050
  enter 2
leftAmount=-480    i=3, billNumber=2, bills 5, 0, 3, 0, sum=650
    enter 1
leftAmount=-480      i=0, billNumber=1, bills 5, 0, 3, 0, sum=650
      enter 0
leftAmount=-530        i=5, billNumber=0, bills 5, 0, 3, 0, sum=650
        i=4, billNumber=0, bills 4, 0, 3, 0, sum=640
        i=3, billNumber=0, bills 3, 0, 3, 0, sum=630
        i=2, billNumber=0, bills 2, 0, 3, 0, sum=620
        i=1, billNumber=0, bills 1, 0, 3, 0, sum=610
        i=0, billNumber=0, bills 0, 0, 3, 0, sum=600
    i=2, billNumber=2, bills 5, 0, 2, 0, sum=450
    enter 1
leftAmount=-480      i=0, billNumber=1, bills 5, 0, 2, 0, sum=450
      enter 0
leftAmount=-530        i=5, billNumber=0, bills 5, 0, 2, 0, sum=450
        i=4, billNumber=0, bills 4, 0, 2, 0, sum=440
        i=3, billNumber=0, bills 3, 0, 2, 0, sum=430
        i=2, billNumber=0, bills 2, 0, 2, 0, sum=420
        i=1, billNumber=0, bills 1, 0, 2, 0, sum=410
        i=0, billNumber=0, bills 0, 0, 2, 0, sum=400
    i=1, billNumber=2, bills 5, 0, 1, 0, sum=250
    enter 1
leftAmount=-480      i=0, billNumber=1, bills 5, 0, 1, 0, sum=250
      enter 0
leftAmount=-530        i=5, billNumber=0, bills 5, 0, 1, 0, sum=250
        i=4, billNumber=0, bills 4, 0, 1, 0, sum=240
        i=3, billNumber=0, bills 3, 0, 1, 0, sum=230
        i=2, billNumber=0, bills 2, 0, 1, 0, sum=220
        i=1, billNumber=0, bills 1, 0, 1, 0, sum=210
        i=0, billNumber=0, bills 0, 0, 1, 0, sum=200
    i=0, billNumber=2, bills 5, 0, 0, 0, sum=50
    enter 1
leftAmount=-480      i=0, billNumber=1, bills 5, 0, 0, 0, sum=50
      enter 0
leftAmount=-530        i=5, billNumber=0, bills 5, 0, 0, 0, sum=50
        i=4, billNumber=0, bills 4, 0, 0, 0, sum=40
        i=3, billNumber=0, bills 3, 0, 0, 0, sum=30
        i=2, billNumber=0, bills 2, 0, 0, 0, sum=20
        i=1, billNumber=0, bills 1, 0, 0, 0, sum=10
        i=0, billNumber=0, bills 0, 0, 0, 0, sum=0

66
https://ideone.com/KO3OZL
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!