fork download
copy 
  1. <?php
  2. //Дан массив пар числел, например ((0.08, -0.12), (0.07, -0.13), (0.03, -0.7), (0.14, -0.2)). 
  3. //Надо из каждой пары выбрать одно число так, чтобы сумма всех выбранных чисел была минимальной не отрицательной.
  4.  
  5. $input = array(
  6. 	[0.08, -0.12],
  7. 	[0.07, -0.13],
  8. 	[0.03, -0.7],
  9. 	[0.14, -0.2],
  10. 	//[0.11, 0.1],
  11. 	//[-0.05, -0.08],
  12. 	//[-0.1, -0.02]
  13. );
  14.  
  15. $log = count($input);
  16. $iterations = pow(2, $log);
  17.  
  18. $results = [];
  19.  
  20. for ($i = 0; $i < $iterations; $i++) {
  21.  
  22. 	$map = decbin($i);
  23.  
  24. 	$map = str_pad($map, $log, "0", STR_PAD_LEFT);
  25.  
  26. 	$map = preg_split('//u', $map, null, PREG_SPLIT_NO_EMPTY);
  27.  
  28.  
  29.  
  30. 	$result = 0;
  31. 	$resultString = '';
  32.  
  33. 	for ($j = 0; $j < $log; $j++) {
  34.  
  35. 		$addr = $map[$j];
  36. 		$addedNum = $input[$j][$addr];
  37. 		$result += intval($addedNum * 1000);
  38. 		$resultString .= $addedNum . " ";
  39. 	}
  40.  
  41. 	if ($result > 0) {
  42. 		$results["$resultString"] = $result/1000;
  43. 	} 
  44.  
  45. }
  46.  
  47. arsort($results);
  48.  
  49. $return = [];
  50. $min = min($results);
  51.  
  52. foreach ($results as $name => $value) {
  53.  
  54. 	if (abs(($value-$min)/$min) < 0.00001) {
  55. 		$return[$name] = $value;
  56. 	}
  57. }
  58.  
  59. var_dump($return);
Success #stdin #stdout 0.01s 82944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
array(2) {
  ["0.08 -0.13 0.03 0.14 "]=>
  float(0.12)
  ["-0.12 0.07 0.03 0.14 "]=>
  float(0.12)
}
https://ideone.com/2j90ze
language:
PHP (php 7.3.5)
created:
6 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!