Was ist der schnellste Algorithmus zum Auffinden von Teilmengen, die sich zu einer Zahl addieren?

Ich versuche ein Modell zu erstellen, das das Ergebnis der Wahl 2016 vorhersagt. Ein Algorithmus, den ich brauche, ist der, alle möglichen Kombinationen von Staaten zu finden, die bis zu 270 Wahlstimmen ergeben können. So ist die Einrichtung wieWas ist der schnellste Algorithmus zum Auffinden von Teilmengen, die sich zu einer Zahl addieren?

const electoralVotesToWin = 270; 
const states = [ 
    { Name: "Virginia", ElectoralVotes: 13 }, 
    { Name: "North Carolina", ElectoralVotes: 15 }, 
    ... 
];

und mein gewünschtes Ergebnis ist wie

var stateCombos = [ 
    [ "Virginia", "North Carolina", ... ], 
    [ "Virginia", "North Carolina", ....], 
    ... 
];

Lassen Sie mich wissen, wenn ich es besser erklären muß.

Gibt es einen besseren Algorithmus als den Brute-Force-Ansatz, der jede Teilmenge von Zuständen findet? Wie auch immer, hier hat jeder eine elegante und kompakte, aber nicht unbedingt effiziente Lösung?

Quelle

2016-06-30 user6048670

das ist ein klassisches 0-1 Knapsack Problem mit Gewicht == Größe. Siehe https://en.wikipedia.org/wiki/Knapsack_problem. Für die Gesamtgröße von 270 und die Positionsnummer <= Anzahl der Zustände sollte ein einfacher DP Ihnen sofort das Ergebnis geben. Jemand hat sogar die gleiche Frage zu quora https://www.quora.com/Is-there-a-way-to-print-out-all-solutions-to-the-0-1-Knapsack-problem- gestellt -dynamic-programming-in-O-nC-Zeit – lavin

Zu @ Lavins Kommentar hinzufügen: Das Problem, * eine * Menge von Zuständen zu finden, deren Votes sich auf genau 270 addieren, ist NP-schwer, aber (wenn eine solche Menge von Zuständen existiert), finden Sie * eine solche * Lösung für dieses spezielle Problem sehr schnell unter Verwendung des DP-Algorithmus, der bei diesem Link angegeben ist. Das Finden von * allen * Lösungen ist auch "schnell" - im Sinne von O (n) pro Lösung, durch Zurückverfolgen der DP-Matrix - aber es könnte eine exponentielle Anzahl von ihnen geben. Auch wenn Sie alle Lösungen finden möchten, die * mindestens * 270 ergeben, müssen Sie die DP-Wiederholung geringfügig ändern. –

@lavin ist nicht das Problem mit dem Rucksack, eine Kombination zu finden, die das Gewicht maximiert, während sie unter dem gegebenen Limit bleibt - während OP nach allen Kombinationen fragt, die genau die gegebene Grenze summieren? –

Dies kann einige weitere Live-Tests benötigen, aber eine rekursive Funktion verwendet werden könnten Kombinationen zu erstellen, bis das Ziel (oder in dieser Implementierung, bis kein Rest ist) erreicht ist:

function getStates(arr, rem){  
    var res = [], el; 
    while(arr.length){ 
     [el, ...arr] = arr;   
     if(el.ElectoralVotes >= rem) 
      res.push([el]); //total reached 
     else{ 
     for(var s of getStates(arr,rem - el.ElectoralVotes)) //try to reach total with remainder   
      res.push([el, ...s]); 
     } 
    } 
    return res; 
} 


var res= getStates(states, electoralVotesToWin);

Test fiddle

NB, das ursprüngliche Objekt zum testen verwendet wurde, sondern nur die Namen zu bekommen, einfach die Linien ändern, wo das Element in das Array geschoben wird, so dass nur der Name gedrückt wird, zum Beispiel: fiddle

Quelle

2016-06-30 17:33:28

Was ist der schnellste Algorithmus zum Auffinden von Teilmengen, die sich zu einer Zahl addieren?

Antwort

Verwandte Themen