fork(3) download 
  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) {
  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. 	$amount = $amount - $currentBill*$currentMaxBills;
  43.  
  44. 	for ($i = $currentMaxBills; $i >= 0; $i--) {
  45.  
  46. 		$attempts++;
  47. 		$billsCopy = $bills;
  48. 		$billsCopy[$currentBill] = $i;
  49.  
  50. 		$sum = countBillsSum($billsCopy);
  51. 		//echo "{$debugOffset}  i=$i, bills ".implode(", ", $billsCopy).", sum=$sum\n";
  52.  
  53. 		if ($billNumber > 0) { 
  54. 			$x = findChange($amount, $keysBills, $billsCopy, $billNumber - 1);
  55. 			if ($x) {
  56. 				return $x;
  57. 			}
  58. 		} elseif ($amount == 0) {
  59. 			//echo "{$debugOffset}  MATCH ".implode(", ", array_values($billsCopy))." (sum=$sum)\n";
  60. 			$x = implode(", ", array_values($billsCopy));
  61. 			return $x;
  62. 		} 
  63. 	}
  64. }
  65.  
  66. echo findChange($amount, $keysBills, $bills, 3);
  67. echo "\n".$attempts;
Success #stdin #stdout 0.01s 20568KB
comments (?)
stdin 
Standard input is empty
stdout 
18
https://ideone.com/6ORNmR
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!