Ich möchte, dass ein Algorithmus (keine bestimmte Sprache) eine Teilmenge aus einer Menge von Ganzzahlen so findet, dass ihre Summe innerhalb eines bestimmten Bereichs liegt.

Zum Beispiel, wenn ich eine Gruppe von Menschen habe, deren Gewichte wie folgt sind.

var people:{
   jane:126,
   julia:112,
   charles:98,
   john:182,
   bob:213,
   edgar: 237,
   jay: 223,
   dan: 191,
   alex: 210,
   david: 196
}

Nun, von diesen Leuten würde ich gerne eine Untergruppe finden, deren Gesamtgewicht zwischen 818 und 822 Pfund liegt (Wenn Sie versuchen zu rechnen ... stören Sie sich nicht, diese Zahlen sind aus meinem Kopf und Ich weiß nicht einmal, ob es eine Lösung für diesen Datensatz gibt. Die Anzahl der Personen in der Gruppe spielt keine Rolle, nur eine Gruppe aus der größeren Gruppe. Und wirklich, jede Gruppe wird es tun (obwohl zufällig in meinem Fall besser ist).

Beachten Sie, dass dies nur ein kurzes Beispiel ist. Es würde tatsächlich Hunderte von Menschen geben, und es wäre möglich, dass es keine Kombination gibt, die diesen Kriterien entspricht. Da die tatsächlichen Zahlen viel größer wären, mache ich mir Sorgen um ein n ^ n-Problem und durchlaufe Tausende von Iterationen, obwohl ich dies brauche, um sehr schnell zu laufen.

Vielleicht bin ich an diesem Tag im Informatikunterricht eingeschlafen, aber ich konnte mir nichts anderes als Brute-Force-Methoden einfallen lassen.

Ich habe dies als Javascript markiert, einfach weil dies meiner tatsächlichen Implementierung am nächsten kommt (und es leichter zu lesen ist). Offen für andere Lösungen, solange sie nicht irgendwo auf einer Cthulhu-Funktion beruhen.

Ich weiß, dass dies eine seltsame Frage zu SO ist, aber jede Hilfe hier wäre dankbar.


Ok, ich bin ratlos. 23 Stunden, um ein Kopfgeld für etwas zu veröffentlichen, das ich in Bezug auf Code groken kann - mein Hintergrund liegt sicherlich nicht in diesem Bereich, und es fällt mir schwer, selbst die Notationen zu erkennen, die zur Beschreibung des Problems verwendet werden, geschweige denn die Lösungen.

Möchte mir jemand helfen und mir einen Beispiel-Javascript-Code geben, den ich für das endgültige Projekt ändern kann? Ich werde ein Kopfgeld von 250pt hinzufügen, wenn ich kann ... aber wenn eine anständige Lösung durchkommt, werde ich es verteilen, wenn es soweit ist.

14
John Green 10 Okt. 2012 im 00:23

4 Antworten

Beste Antwort

Dies ähnelt dem 0-1-Rucksackproblem oder Teilmengenproblem.

Wenn Gewichte keine sehr großen Ganzzahlen sind, sollte eine dynamische Programmierlösung effizient sein.


Hier ist die Javascript-Implementierung des dynamischen Programmieralgorithmus. Wenn Sie zufällige Gruppen möchten, mischen Sie einfach die Liste der Personen nach dem Zufallsprinzip, bevor Sie diesen Algorithmus anwenden.

var p = {
   jane:126,
   julia:112,
...
};

function subset(people, min, max)
{
  var subsets = [];
  subsets[0] = '';

  for (var person in people)
  {
    for (var s = min-1; s >= 0; --s)
    {
      if (s in subsets)
      {
        var sum = s + people[person];

        if (!(sum in subsets))
        {
          subsets[sum] = subsets[s] + ' ' + person;

          if (sum >= min && sum <= max)
          {
            return subsets[sum];
          }
        }
      }
    }
  }

  return 'Not found';
}

print(subset(p, 818, 822));
10
Evgeny Kluev 12 Okt. 2012 im 12:42

Hier finden Sie eine Antwort auf eine ähnliche Frage: Finde Kombination (en) der Summe (n) von Elementen in einem Array, deren Summe einer bestimmten Zahl entspricht

<?php

$limit = 12;
$array = array(6,1,10,4,1,3,11,2,15,5,12,10,17);

echo implode(', ',$array).'<br>';

// remove items 15 and 17 because they are great then $limit = 12
$array = array_filter($array, function($var) use ($limit) {
  return ($var <= $limit);
});

rsort($array);
echo implode(', ',$array);

// the algorithm is usable if the number of elements is less than 20 (because set_time_limit)
$num = count($array); 

//The total number of possible combinations 
$total = pow(2, $num);

$out = array();

// algorithm from http://r.je/php-find-every-combination.html
// loop through each possible combination  
for ($i = 0; $i < $total; $i++) {  

    $comb = array();

    // for each combination check if each bit is set 
    for ($j = 0; $j < $num; $j++) { 
       // is bit $j set in $i? 
        if (pow(2, $j) & $i){
          $comb[] = $array[$j];
        }      
    } 

    if (array_sum($comb) == $limit)
    {
      $out[] = $comb;
    }
}

array_multisort(array_map('count', $out), SORT_ASC, $out);

$out = array_unique($out, SORT_REGULAR);

foreach($out as $result) echo implode(', ', $result).'<br>';

Die Ausgabe dieses Codes ist eine Liste von Kombinationen, deren Summe nur $ limit (12) ist ...

12
10, 2
11, 1
5, 4, 3
6, 4, 2
6, 5, 1
10, 1, 1
5, 4, 2, 1
6, 3, 2, 1
6, 4, 1, 1
5, 3, 2, 1, 1
1
Community 23 Mai 2017 im 12:05

Es sieht aus wie eine Variation des "binären Rucksackproblems" mit der zusätzlichen Grenze, dass die Antwort abgelehnt wird, wenn die beste Anpassung immer noch außerhalb des akzeptablen Bereichs liegt.

Möglicherweise möchten Sie sich mit "Polynomzeitnäherungen" befassen.

Ein Ansatz könnte darin bestehen, den Satz nach Gewicht zu sortieren. Dann fängst du an, von der Mitte nach unten und oben zu schauen: du bekommst Dan, John, David, Alex und du bist bei 779. Du fügst Jane hinzu und findest dich bei 905 und das ist zu viel um 87; Also überprüfst du den Namen unten, Julia, das ist 112, und siehst die engste Übereinstimmung zwischen den Unterschieden. Wenn Sie Alex mit Julia (210-112) austauschen, verlieren Sie 98, wenn Sie David mit Julia austauschen, verlieren Sie 84. Schäumen, spülen, wiederholen.

Der Algorithmus ist O (n log n) zum Sortieren und hängt dann von der eingestellten Größe ab. Es hat mehrere Nachteile (es wird nicht garantiert, dass sie konvergieren, Gruppen sind in der Regel zusammenhängend, es werden Personen in der Nähe des Startpunkts versammelt usw.), aber wenn Sie nur "eine Gruppe" wollen, könnte dies ausreichen.

Sie können den Algorithmus auch rekursiv implementieren. Der schlimmste Fall wäre O (n ^ 3 log n), aber wenn Sie wirklich mit Menschen arbeiten (Gewichte in relativ kleinen Bereichen, glatte Kurve), ist die Konvergenz wahrscheinlich ziemlich schnell.

4
LSerni 9 Okt. 2012 im 20:51

Dies nenne ich ein "Sort and Bracket" -Problem. Sie lösen es, indem Sie die Daten sortieren und dann um den Zielwert oder den Zielbereich klammern.

In diesem Fall lautet die sortierte Reihenfolge beispielsweise:

98
112
126
182
191
196
210
213
223
237

Jetzt mitteln Sie die Liste: 178,8. Daher ist die Starthalterung (126,182). Bewegen Sie sich von diesem Durchschnitt weg: Summe (126.182.112.191,98) = 709, zu klein. Löschen Sie die 98 und ersetzen Sie sie durch den Wert von der anderen Seite: 196, dh Summe (126.182.112.191.196) = 807, immer noch zu klein. Gehen Sie zum nächsten Wert auf der oberen Seite, Summe (126.182.112.191.210) = 821. Ok, habe ein Match gefunden. Wenn Sie diesen Vorgang fortsetzen, können Sie jede Übereinstimmung finden. Grundsätzlich hilft Ihnen die Belichtungsreihe dabei, nur eine Teilmenge aller möglichen Kombinationen zu durchsuchen, damit Sie nicht jede Kombination überprüfen müssen. Sie generieren Kombinationen nach außen aus einem Durchschnitt anstatt aus dem einen oder anderen Ende.

Immer wenn Ihre Summe den Bereich überschreitet / unterschreitet, beenden Sie die Kombinationsgenerierung auf der High / Low-Seite und wechseln zur anderen. Dies ist die optimale Lösung für das Problem.

Implementierungsmethode: Um diesen Algorithmus zu implementieren, benötigen Sie einen Kombinationsgenerator, der in "lexikografischer" Reihenfolge arbeitet. Sie beginnen dann mit n, sagen wir 5 Elementen, und bestimmen die Median-Kombination, wie ich oben gezeigt habe. Sie erhalten dann die nächstniedrigere Kombination. Wenn Sie niedrig sind, wechseln Sie zur nächsthöheren Kombination und so weiter.

-------------- ADDENDUM -------------------

Nachdem Sie darüber nachgedacht haben, ist es möglicherweise besser, einen einfachen Algorithmus vom Typ Änderungen zu verwenden, als einen lexikografischen Kombinator. Diese Art von Algorithmus generiert alle Kombinationen, wechselt jedoch jeweils nur zwei Elemente. Grundsätzlich ändern Sie diesen Algorithmus, um die Richtung zu ändern, wenn er außerhalb der Grenzen liegt (über oder unter dem Bereich).

3
Tyler Durden 9 Okt. 2012 im 21:57