Knapsack: Eine Einschränkung, jedes Element kann nur einmal ausgewählt werden, mit einer großen Anzahl von Elementen

Question

Ich schreibe einen Algorithmus, der die Rucksack-Problemform nimmt. Ich versuche den Wert (V) meines Rucksacks bei maximalem Gewicht (W) zu maximieren. Die Fänge sind, dass jeder Gegenstand (I) nur einmal ausgewählt werden kann, der Rucksack unabhängig vom Gewicht kann nur 10 Gegenstände halten, und es gibt eine sehr große Anzahl von Gegenständen (500+).

Meine Gedanken waren bis jetzt, einen Rucksack zu erzeugen, der übergewichtig ist und rekursiv rückwärts arbeitet, indem er Artikel eins nach dem anderen ersetzt, bis es < = das maximale Gewicht ist. Dies ist kein Problem, um den optimalsten Rucksack zu erzeugen, jedoch möchte ich wirklich die folgenden 100 Rucksäcke erzeugen. Ich dachte, dass ich dies tun könnte, indem ich meinen rekursiven Prozess fortsetze, jedoch habe ich nicht das Gefühl, dass dies völlig korrekt ist, da möglicherweise etwas mehr optimale Rucksäcke fehlen.

Answer 1

Dieses Problem kann als Ganzzahl-Programm formuliert werden.

maximize sum_{i in items} v_i * x_i 
subject to 
sum_{i in items} x_i <= 10  [u] 
sum_{i in items} w_i * x_i <= W [z] 
for all i in items, x_i in {0, 1} [y_i] 

Es gibt viele Solver-Bibliotheken, die dieses Programm für Sie lösen werden; Alternativ können Sie die branch and bound selbst tun. Hier ist das duale lineare Programm, das gelöst werden kann, um eine Obergrenze für den objektiven Wert des ganzzahligen Programms zu erhalten, die für Verzweigung und Grenze benötigt wird.

minimize 10 * u + W * z + sum_{i in items} y_i 
subject to 
for all i in items, u + w_i * z + y_i >= v_i [x_i] 
u >= 0 
z >= 0 
for all i in items, y_i >= 0 

Wert für z, Gegeben ist eine Frage, die anderen Variablen Einstellung von positiven y_i zu dem neun Top-Artikel von v_i - w_i * z zuweisen, während u Zuordnung der zehnte größte Wert. Es sollte möglich sein, ternär nach z in Zeit O(n log n) zu suchen.