Jak to ugryźć , zbiór liczb i szukanie czy część suma części z nich da daną liczbę., Nie mam pomysłu Opcje

[icemanwlkp]

Witam , mam taki problem . Jest tabela z liczbami z dwoma miejscami po przecinku . I teraz mam napisać skrypt który wyłowi liczby z tej tablicy których suma da daną liczbę , lub stwierdzić iż nie ma takiej kombinacji .
Jak zabrać się do takiego skryptu ? Jakieś pomysły podpowiedzi ?

Przykład:

[PHP] pobierz, plaintext 
$liczby = Array("2.56","1.74","1.69","2.44","1.53","2.45","1.21","2.62","2.33","1.21","2.69","3.24","1.87","1.75","2.02","1.80","1.78");
$szukana = '20.00';
[PHP] pobierz, plaintext 

[nospor]

Tworzysz wszelkie mozliwe kombinacje sum i sprawdzasz ktora daje to czego szukasz
Oczywiscie mozesz to zoptymalizowac, np. gdy dana suma jest juz wieksza, to nie dokladasz kolejnych kombinacji do niej.

[icemanwlkp]

I nadal mam pustkę w głowie jak to rozpisać w php ? Zwłaszcza, że może to być tylko część liczb z tablicy .

[nospor]

Nie bardzo rozumiem. Nie wiesz jak zrobic wszystkie mozliwe kombinacje ze zbioru?

[markonix]

http://stackoverflow.com/questions/1083439...ons-of-1d-array

[Pyton_000]

Śmierdzi mi tu Amino, czyż nie ?

[Crozin]

1. Na początek przemnóż sobie wszystkie liczby przez 100 by operować na liczbach całkowitych - ewentualnie przy wyświetlaniu podziel ponownie wszystko przez 100. Porównywanie liczb zmiennoprzecinkowych jest problematyczne - https://www.google.pl/search?q=what+every+p...me&ie=UTF-8
2. http://stackoverflow.com/questions/4632322...ach-a-given-sum

[nospor]

@Crozin niestety autor tematu nie oczekuje algorytmu tylko gotowego kodu w php.
Nawet jak dostal gotowce od markonix to ma problem bo tam sa teksty a nie liczby.

Tak wiec albo dajcie gotowca albo oszczedzcie sobie czasu na postowanie

@Pyton rozwin watek

@iceman
to jest bardzo mile
http://www.php.net/manual/en/function.shuffle.php#90615
zamiast tekstow wstaw liczby i masz rozwiazanie... no procz sum. Ale kurka, cos moglbys zrobic samodzielnie

[lukaskolista]

Nie wiem czy o to chodzi, tak bardzo ale to bardzo na szybko:

[PHP] pobierz, plaintext 
<?php
 
$numbers = [1.11, 2.22, 3.33];
$expectedSum = 5.55;
 
foreach ($numbers as $firstKey => $firstNumber) {
	foreach ($numbers as $secondKey => $secondNumber) {
		if ($firstKey !== $secondKey && (string) ($firstNumber + $secondNumber) == (string)$expectedSum) {
			echo 'Found: '.$firstNumber.' and '.$secondNumber;
			exit;
		}
	}
}
[PHP] pobierz, plaintext 

[Pyton_000]

@nospor chodziło o to że Amino jakiś czas temu w zupkach dawał kwoty. I jak się uzbierało np. 100 to można było wymienić na kasę Warunkiem było uzyskanie pełnych kwot. a problem polegał na tym że właśnie były takie śmieszne sumy i zawsze albo brakowało troszkę albo za dużo

[nospor]

@lukaskolista przeciez twoje rozwiazanie sumuje tylko dwie liczby

@Pyton

[icemanwlkp]

Nie do Amino ,ale księgowa mnie meczy odnośnie takich dupereli.

Napisłem tyle ,ale tylko nei wiem czy włąściwie no i nie wiem jak wyświetlić użyte liczby tu mi nie znajduje wyniku 2000 .

[PHP] pobierz, plaintext 
$tabelka =  Array(256,174,169,244,153,245,121,262,233,121,269,324,187,175,202,180,178);
$tabelka2 = $tabelka;
 
for ($x=0;$x<count($tabelka);$x++)
{
    $nsuma = 0;
    for ($y=$x+1;$y<count($tabelka2);$y++)
    {
        $suma = $tabelka[$x]+$tabelka2[$y];
        $nsuma += $tabelka[$x]+$tabelka2[$y];
        echo $suma.'<br>';
        echo $nsuma.'<br>';
    }
}
[PHP] pobierz, plaintext 

[nospor]

Dostales gotowe kody, szczegolnie fajny ten co ci podalem jako ostatni.
To co napisales ma sie srednio do twojego problemu

[markonix]

Weź mój przykład, zamiast tekstu rób tablice, będziesz miał tablicę wszystkich możliwych kombinacji bez powtórzeń, potem tylko foreach + break w momencie znalezienia pierwszej kombinacji, która spełnia warunek tej sumy.
Jeżeli foreach przeleci bez break oznacza to brak.

[icemanwlkp]

Cosik mi nie wychodzi , kurka ... wyniki , są ale jakby sklejone do siebie

[PHP] pobierz, plaintext 
$array = array(1,2,3,4,5,6,7,8,9);
 
function depth_picker($arr, $temp_string, &$collect) {
    if ($temp_string != "") 
        $collect []= $temp_string;
 
    for ($i=0; $i<sizeof($arr);$i++) {
        $arrcopy = $arr;
        $elem = array_splice($arrcopy, $i, 1);
        if (sizeof($arrcopy) > 0) {
            depth_picker($arrcopy, $temp_string[]=$elem[0], $collect);
        } else {
            $collect []= $temp_string[]=$elem[0];
        }   
    }   
}
 
$collect = array();
depth_picker($array, "", $collect);
print_r($collect);
[PHP] pobierz, plaintext 

[nospor]

Wlasnie sprawdzilem przyklad do ktorego cie odeslalem. Dziala bez zadnych przerobek. Tylko skopiowac i wkleic do siebie. Widze lubisz sobie na sile utrudniac zycie

[icemanwlkp]

Dla 5 liczb działa , powyżej nie wywala już nic , gdzie tkwi problem ?

[PHP] pobierz, plaintext 
    function power_perms($arr) {
 
    $power_set = power_set($arr);
    $result = array();
    foreach($power_set as $set) {
        $perms = perms($set);
        $result = array_merge($result,$perms);
    }
    return $result;
}
 
function power_set($in,$minLength = 1) {
 
   $count = count($in);
   $members = pow(2,$count);
   $return = array();
   for ($i = 0; $i < $members; $i++) {
      $b = sprintf("%0".$count."b",$i);
      $out = array();
      for ($j = 0; $j < $count; $j++) {
         if ($b{$j} == '1') $out[] = $in[$j];
      }
      if (count($out) >= $minLength) {
         $return[] = $out;
      }
   }
 
   //usort($return,"cmp");  //can sort here by length
   return $return;
}
 
function factorial($int){
   if($int < 2) {
       return 1;
   }
 
   for($f = 2; $int-1 > 1; $f *= $int--);
 
   return $f;
}
 
function perm($arr, $nth = null) {
 
    if ($nth === null) {
        return perms($arr);
    }
 
    $result = array();
    $length = count($arr);
 
    while ($length--) {
        $f = factorial($length);
        $p = floor($nth / $f);
        $result[] = $arr[$p];
        array_delete_by_key($arr, $p);
        $nth -= $p * $f;
    }
 
    $result = array_merge($result,$arr);
    return $result;
}
 
function perms($arr) {
    $p = array();
    for ($i=0; $i < factorial(count($arr)); $i++) {
        $p[] = perm($arr, $i);
    }
    return $p;
}
 
function array_delete_by_key(&$array, $delete_key, $use_old_keys = FALSE) {
 
    unset($array[$delete_key]);
 
    if(!$use_old_keys) {
        $array = array_values($array);
    }
 
    return TRUE;
}
 
  $in = array("256","174","169","244","153","245","121","262","233","121","269","324","187","175","202","180","178");
  $power_perms = power_perms($in);    
 
  foreach ($power_perms as $p)
  {
      print_r($p);
      echo '<br>';
  }
[PHP] pobierz, plaintext 

[nospor]

MI tam dziala do 12. Potem sie wywala spowodu pamieci. Zwieksz pamiec

[icemanwlkp]

ini_set("memory_limit",-1); wstawiłem realnie przy 128 GB pamięci , ile liczb mogę brać pod uwagę ? rozumiem, że 1000 liczb to 1000 do potęgi 1000 , czyli tragicznie to będzie długo się robić i raczej zapcha pamięć .

[nospor]

Dlatego w pierwszym poscie wspomnialem o optymalizacji takich skryptow, by nie szukaly dalej gdy suma zostanie osiagnieta. To oszczedzi sporo czasu i pamieci.
Crozin w swoim poscie zapodal ciekawego linka. Niestety nie ma kodu w php. Trzeba przerobic.

[icemanwlkp]

No w sumie tworzy się sporo tablic zbędnych , ale to nie realne przy 10 000 licz gdzie może się okazać ,że nie ma właściwej konfiguracji , czyli skrypt przeleci po wszystkim , jedynie można by określić wstępnie minimalną i maksymalną liczbę liczb jakie muszą być w tablicy

[nospor]

że nie ma właściwej konfiguracji

Nie ze nie ma wlasciwej, ale gdy wszystkie sumy sa ponizej zakladanej. Drobna roznica. Tylko w tym przypadku, gdy wszystkie sumy sa mniejsze to skrypt przeleci wszystkie kombinacje