Login

***Arne Drews*** · 08.06.2016, 10:40

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

**mermshaus** · Registriert seit: 20.03.2015 | Themen: 3 | Beiträge: 50

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(0, 10000);
}

sort($numbers);

$tmp = $numbers;
shuffle($tmp);

$sumToFind = array_sum(array_slice($tmp, 0, $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

***Arne Drews*** · Registriert seit: 18.03.2015 | Themen: 59 | Beiträge: 364

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

Till · 15.06.2016, 12:28

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.

**mermshaus** · Registriert seit: 20.03.2015 | Themen: 3 | Beiträge: 50

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.

**tkausl** · Registriert seit: 19.03.2015 | Themen: 6 | Beiträge: 37

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.

***Arne Drews*** · 22.06.2016, 12:50

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

Login
Benutzername/E-Mail:
Passwort:	Passwort vergessen?
	Merken