alle Kombinationen finden, die die Bedingung erfüllt?

Question

Mein Problem kann wie folgt vereinfacht werden.

Es gibt s Bins, und innerhalb jedes Bins gibt es k Zahlen.
Eine Kombination besteht aus einer Nummer aus jedem Fach, insgesamt also k^s mögliche Kombinationen.
Die Punktzahl einer Kombination ist die Summe von s Zahlen, die es enthält.

Wie kann ich alle Kombinationen mit einem Wert unter einem Wert von r finden?

---

Gerade jetzt, was ich tue ist,
1) in jedem Fach die Zahlen sortieren.
2) Beginnen Sie mit einer Prioritätswarteschlange, die nur die Kombination der kleinsten Zahl aus jedem Fach enthält.
3) rufen Sie eine Kombination aus der Warteschlange auf, fügen Sie s untergeordnete Elemente dieser Kombination hinzu, um sie in die Warteschlange aufzunehmen. (Ein Kind einer Kombination besteht aus dem Ersetzen einer Nummer der Kombination durch die nächst größere Zahl in demselben Fach, also s Kinder einer Kombination.)
4) Wiederholen Sie 3) bis die Kombination größer als ist r. Wenn wir n Kombinationen kleiner als r finden, ist die zeitliche Komplexität dieses Algorithmus dann O(nlog(s-1)n + sklogk).

Natürlich ist dieser Algorithmus nicht optimal. Anstatt beispielsweise mit der kleinsten Kombination zu beginnen, können wir mit einer bekannten unteren Grenze beginnen. Und ich habe das Gefühl, dass dynamische Programmierung auch hier angewendet werden kann, aber ich habe nicht herausgefunden, wie es geht.

Alle Vorschläge sind willkommen, danke.

Answer 1

Nachdem Sie die Klassen sortiert haben, können Sie einen rekursiven Algorithmus verwenden, der eine Teilauswahl um ein Element aus der nächsten Klasse erweitert, bis die Auswahl abgeschlossen ist (oder die Summengrenze überschreitet). Wenn Sie fertig sind, wird es zum Ergebnis hinzugefügt. Durch Backtracking werden alle gültigen Selektionen zum Ergebnis hinzugefügt.

Hier ist ein Pseudo-Code. Das letzte Argument ist sowohl Eingang und Ausgang:

function combinations(int[][] bins, int r, int[] selection, int[][] result): 
    if r < 0 then: 
     return 
    if selection.length >= bins.length then: 
     result.add(selection) 
     return 
    bin = bins[selection.length] 
    for (i = 0; i < bin.length; i++): 
     # Concatenate the i-th value from the bin to a new selection array 
     combinations(bins, r - bin[i], selection + bin[i], result) 

Hier eine Implementierung in JavaScript ist:

function sortBins(bins) { 
 
    for (bin of bins) { 
 
    bin.sort(function (a,b) { return a-b; }); 
 
    } 
 
} 
 

 
function combinations(bins, r, selection, result) { 
 
    if (r < 0) return result; // nothing added to result 
 
    if (selection.length >= bins.length) return result.concat([selection]); 
 

 
    var bin = bins[selection.length]; 
 
    for (var i = 0; i < bin.length; i++) 
 
    result = combinations(bins, r - bin[i], selection.concat([bin[i]]), result); 
 
    return result; 
 
} 
 

 
// Test data: 
 
var r = 13; 
 
var bins = [ 
 
    [5, 2, 3], 
 
    [9, 4, 1], 
 
    [6, 5, 7] 
 
]; 
 
// Get solution: 
 
sortBins(bins); 
 
var result = combinations(bins, r, [], []); 
 
// Output results: 
 
console.log(result);