PHP rocks! wünscht allen Mitgliedern einen guten Rutsch ins neue Jahr 2017 !!!
Hinweis: Das Forum zieht um! Um keine Datenverluste zu haben, schalten wir zwecks Übernahme der Daten das Forum am Sonntag, den 24.04.2016 um ca. 21:00 Uhr offline und passen anschliessend die DNS-Einträge an.
www.php-rocks.de wird euch dann nach den Aktualisierungen der DNS-Server wieder wie gewohnt uneingeschränkt zur Verfügung stehen.
Danke für euer Verständnis!

Themabewertung:
  • 0 Bewertung(en) - 0 im Durchschnitt
  • 1
  • 2
  • 3
  • 4
  • 5
Aus einer Vielzahl an Werten eine bestimmte Summe errechnen
#1
Hallo,

Ich habe mal Anforderung, die eher auf mathematischer Logik basiert.
Es gibt eine Menge an Einzelwerten, aus denen ich eine Summe herausfinden muß.

Beispiel:
Ausgabe:
Einzelwerte:
46.93
78.44
9.01
46.93
334.37
19.90
usw.
Jetzt habe ich eine Summe von bspw. 515.68 und muß herausfinden, aus welchen Werten der Liste sich diese zusammensetzen "könnte".
In diesem Fall war es "zu Fuß" noch relativ einfach ( 334.37 + 9.01 + 46.93 + 46.93 + 78.44 ), aber ich habe weitere solcher Fälle, bei denen ich das nicht so leicht hinbekomme.

Auf welcher mathematischen Logik basierend kann ich das in PHP umsetzen?
Danke
Antworten
#2
Geht in den Bereich der Kombinatorik. Backtracking wäre wohl ein sinnvoller Ansatz.

- https://de.wikipedia.org/wiki/Backtracking

Um wie viele Werte handelt es sich denn?

Hier eine zusammengeschusterte Brute-Force-Lösung, die den Algorithmus für „Ziehen ohne Zurücklegen“ nutzt (z. B. Lotto, 6 aus 49), den ich vor Jahren mal gebastelt habe:

(Das ist keine Backtracking-Variante.)

(Edit: Und wo ich schon Lotto erwähne: Alle Angaben sind wie immer ohne Gewähr.)

PHP-Code:
<?php

// Code bis Trennstrich (=======) 1:1 von hier kopiert:
// http://php-de.github.io/jumpto/kombinatorik-loesungen/#alle-kombinationen-einer-bestimmten-anzahl-der-elemente-eines-arrays

/**
 * Calculates the factorial of a given non-negative integer
 *
 * @param  int $n Non-negative integer
 * @return int Factorial of $n
 */
function fac($n)
{
 
   if (!is_int($n) || $n 0) {
 
       throw new InvalidArgumentException(
 
               'n has to be a non-negative (int)');
 
   }

 
   for ($f 1$n 1$n--) {
 
       $f *= $n;
 
   }

 
   return $f;
}

function 
nChooseK($n$k)
{
 
   $top    1;
 
   $bottom 1;

 
   for ($i 0$i $k$i++) {
 
       $top    *= $n $i;
 
       $bottom *= $i 1;
 
   }

 
   return $top $bottom;
}

/**
 * Creates a lookup table for Fibonacci numbers
 *
 * Table size: (N - k + 1) * k
 *
 * @param $n int N
 * @param $k int k
 * @return array Lookup table for this (N choose k)
 */
function calcLookupTable($n$k)
{
 
  $b $n $k 1;
 
  $fib range(0$k 1);

 
  for ($i 0$i count($fib); $i++)
 
  {
 
      $fib[$i] = range(0$b 1);
 
      $fib[$i][0] = 1;
 
  }

 
  for ($x 0$x $k$x++)
 
  {
 
      for ($y 1$y $b$y++)
 
      {
 
          $p = (isset($fib[$x 1][$y])) ? $fib[$x 1][$y] : 0;
 
          $q = (isset($fib[$x][$y 1])) ? $fib[$x][$y 1] : 0;
 
          $fib[$x][$y] = $p $q;
 
      }
 
  }

 
  return $fib;
}

/**
 * Returns path vector by number
 *
 * @param $n int N
 * @param $k int k
 * @param $w int Path number (between 1 and (N choose k))
 * @param $fib array Lookup table for (N choose k) (see calcLookupTable)
 * @return array Path at given index
 */
function getPathByNumber($n$k$w, array $fib)
{
 
  $b $n $k 1;
 
  $x range(0$k 1);

 
  for ($i 0$i $k$i++)
 
  {
 
      $j 1;
 
      $u $fib[$k $i 1][$b $j];
 
      while ($u $w)
 
      {
 
          $j++;
 
          $u += $fib[$k $i 1][$b $j];
 
      }
 
      $x[$i] =  ($i 0) ? $x[$i 1] + $j $j;
 
      $w $w - ($u $fib[$k $i 1][$b $j]);
 
      $b $b $j 1;
 
  }

 
  return $x;
}


// ============================================================================= Ab hier neu


function findShortestSolution($numbers$sumToFind$verbose true)
{
 
   $numberCount count($numbers);

 
   $tries 1;

 
   for ($k 1$k <= $numberCount$k++) {

 
       $w nChooseK($numberCount$k);

 
       if (true === $verbose) {
 
           echo '[' date('Y-m-d H:i:s') . '] Running... k = ' $k ' (' $w " iterations)\n";
 
       }

 
       $fibTable calcLookupTable($numberCount$k);

 
       for ($draw 1$draw <= $w$draw++) {
 
           $path getPathByNumber($numberCount$k$draw$fibTable);

 
           $sumx 0;

 
           foreach ($path as $element) {
 
               $sumx += $numbers[$element 1];
 
           }

 
           if ($sumToFind === $sumx) {
 
               $solution = array();
 
               foreach ($path as $element) {
 
                   $solution[] = $numbers[$element 1];
 
               }

                if (
true === $verbose) {
 
                   echo '[' date('Y-m-d H:i:s') . '] Found solution in ' $tries " tries\n";
                }

 
               return $solution;
 
           }

 
           $tries++;
 
       }
 
   }

 
   return array();
}



// Zum Test: Bilde 20 Zufallszahlen. Wähle daraus zufällig 10 Elemente. Bilde
// die Summe dieser Elemente. Versuche anhand der Summe und der 20 Zufallszahlen
// die 10 Elemente zu finden.

$numberCount 20;
$elementsInSum 10;

for (
$i 0$i $numberCount$i++) {
 
   $numbers[] = rand(010000);
}

sort($numbers);

$tmp $numbers;
shuffle($tmp);

$sumToFind array_sum(array_slice($tmp0$elementsInSum));

$solution findShortestSolution($numbers$sumToFind);

echo 
'Numbers:     ' implode(', '$numbers) . "\n";
echo 
'Sum to find: ' $sumToFind "\n";
echo 
'Shortest solution: ' $sumToFind ' = ' implode(' + '$solution) . "\n"

Code:
[2016-06-08 22:04:49] Running... k = 1 (20 iterations)
[2016-06-08 22:04:49] Running... k = 2 (190 iterations)
[2016-06-08 22:04:49] Running... k = 3 (1140 iterations)
[2016-06-08 22:04:49] Running... k = 4 (4845 iterations)
[2016-06-08 22:04:49] Running... k = 5 (15504 iterations)
[2016-06-08 22:04:49] Running... k = 6 (38760 iterations)
[2016-06-08 22:04:50] Running... k = 7 (77520 iterations)
[2016-06-08 22:04:50] Found solution in 68762 tries
Numbers:     96, 470, 592, 1127, 1325, 1387, 1776, 3752, 4611, 5860, 5923, 6193, 6199, 6684, 7517, 7518, 9581, 9723, 9869, 9878
Sum to find: 40911
Shortest solution: 40911 = 96 + 470 + 5860 + 7517 + 7518 + 9581 + 9869
Antworten
#3
Hi Marc,

Das sieht super aus, danke dafür.
Ich werde mir das morgen mal in Ruhe ansehen, denke aber dass ich damit ans Ziel komme.

Schöne Grüße
Antworten
#4
Ich bin schlecht in Mathe Undecided Also schlagt mich:
Ist es möglich die Werte irgendwie als 2er Potenzen zu normalisieren und das Prinzip einer Bitmask zu verwenden?
Ansonsten würde ich fürs Brute-forcen die Nummern abwärts sortieren und zunächst versuchen die größten Nummern von der Summe zu substraieren und versuchen auf 0 zu kommen.

Aber ihr habt ja schon eine Lösung, sicherlich besser.
Antworten
#5
Till schrieb:Ist es möglich die Werte irgendwie als 2er Potenzen zu normalisieren und das Prinzip einer Bitmask zu verwenden?

Ich glaube nicht, weil Addition meines Wissens keine „bitwise“-Operation (im Sinne von AND, OR, XOR, …) ist. Die Operationen beachten alle keine Überträge, die bei Addition aber relevant sind.

Zitat:Ansonsten würde ich fürs Brute-forcen die Nummern abwärts sortieren und zunächst versuchen die größten Nummern von der Summe zu substraieren und versuchen auf 0 zu kommen.

Es gibt sicherlich einige Optimierungen zu dem von mir vorgeschlagenen Ansatz. Man könnte zum Beispiel vorab alle Zahlen ausschließen, die größer sind als die gesuchte Summe. Das geht möglicherweise sogar in die Richtung dessen, was du beschreibst.

Ich würde im Zweifel bei Bedarf wirklich erst mal schauen, wie sich Backtracking von der Laufzeit her so macht. Das kann ich ohne weitere Recherche nicht einschätzen. Das sind tendenziell wahrscheinlich Problemstellungen, bei denen ein guter Algorithmus mehr bringt als eine Optimierung eines schlechten Algorithmus, bei denen der richtige Ansatz also entscheidend ist. (Ähnlich wie das Verhältnis von BubbleSort zu QuickSort oder so.) Oft bringt es wenig, Faktoren aus der Laufzeit rauszuziehen, weil ein Zehntel von „viel zu langsam“ immer noch viel zu langsam ist.

Zitat:Aber ihr habt ja schon eine  Lösung, sicherlich besser.

Die Lösung ist höchstens „gut genug“. Schnell ist sie nicht gerade. Es hängt letztlich halt auch daran, was der genaue Einsatzzweck ist.
Antworten
#6
Gebe auch mal meinen Senf dazu ab  Smile
http://cpp.sh/2n5q4
Falsche Sprache, ich weiß, tut mir leid.
(Und der Code ist auch nicht der schönste, ist eine 10-minuten spielerei)

Glaube das ist es, was @Till meinte. Von groß nach klein sortieren, dann solange Zahlen (von der grösten beginnend) auf den stack legen bis man entweder die Zahl hat die man sucht oder drüber ist. Ist man drüber nimmt man die oberste Zahl wieder weg und nimmt stattdessen die nächst kleinere zahl. Ist man am Ende der Reihe nimmt man die obersten beiden runter und pusht die nächstkleinere der zweiten, die man runtergenommen hat. wieder drauf.
Antworten
#7
Grundsätzlich ist das nie die falsche Sprache  Big Grin

Danke, das kann ich gut zu C# adaptieren und entsprechend in unserer WaWi zur Verfügung stellen.

Gruß Arne
Antworten


Gehe zu: