fork download 
  1. <?php
  2.  
  3. error_reporting(-1);
  4.  
  5. $amount = 6600;
  6. $bills = [5000, 2000, 500, 200];
  7. $totalBills = [1, 4, 1, 3];
  8. $rndCombination = [0, 0, 0, 0];
  9.  
  10. function nextCombination($total, $combination, $bills, $amount){
  11. 	$n = count($total) - 1;
  12. 	for( ; $n>=0; $n--){
  13. 		if($combination[$n] < $total[$n]){
  14. 			$combination[$n] += 1;
  15. 			break;
  16. 		} else {
  17. 			$combination[$n] = 0;
  18. 		}
  19. 	}
  20. 	return $combination;
  21. }
  22.  
  23. function calculateSum($combination, $bills){
  24. 	$sum = 0;
  25. 	foreach($bills as $k => $v){
  26. 		$sum += $v * $combination[$k];
  27. 	}
  28. 	return $sum;
  29. }
  30.  
  31. function outputCombination($combination, $bills){
  32. 	$str = "";
  33. 	foreach($bills as $k => $v){
  34. 		$str .= "{$v}x{$combination[$k]} ";
  35. 	}
  36. 	return $str;
  37. }
  38.  
  39. $res = nextCombination($totalBills, $rndCombination, $bills, $amount);
  40. $sum = calculateSum($res, $bills, $amount, $totalBills);
  41.  
  42. function Main($res, $sum, $amount, $totalBills, $bills){
  43. 	while($res != $totalBills){
  44. 		if($sum == $amount){
  45. 			$str = outputCombination($res, $bills);
  46. 			echo "Сумма: {$amount}\n";
  47. 			echo "Выдача возможна, число купюр:\n{$str}";
  48. 			exit();
  49. 		} else {
  50. 			$res = nextCombination($totalBills, $res, $bills, $amount);
  51. 			$sum = calculateSum($res, $bills, $amount, $totalBills);
  52. 		}
  53. 	}
  54. 	echo "Выдача невозможна, подходящей комбинации не нашлось.";
  55. }
  56.  
  57. Main($res, $sum, $amount, $totalBills, $bills);
  58.  
Success #stdin #stdout 0.02s 26628KB
comments (?)
stdin 
Standard input is empty
stdout 
Сумма: 6600
Выдача возможна, число купюр:
5000x0 2000x3 500x0 200x3
https://ideone.com/tSOxlD
language:
PHP (php 7.3.5)
created:
3 years ago
visibility:
secret

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!