+ - Rucksackproblem

9

Bestimmen Sie anhand einer Reihe von Elementen mit jeweils einem Gewicht und einem Wert die Anzahl jedes Elements, das in eine Sammlung aufgenommen werden soll, damit das Gesamtgewicht kleiner oder gleich einem bestimmten Grenzwert ist und der Gesamtwert so groß wie möglich ist.

Wikipedia für weitere Informationen

Zum Beispiel können Sie ein maximales Gewicht von 15 und Objekte mit Wert / Masse als erhalten, [5,2], [7,4] [1,1]und Sie würden [7,0,1]7 [5 <value>, 2 <mass>]Objekte und 1 [1 <value>, 1 <mass>]Objekt für eine Punktzahl von 36 ausgeben .

Regeln

Die Eingabe kann in jedem vernünftigen Format erfolgen

Ausgabe ist auch flexibles Format,

Sie dürfen keine Bibliotheken verwenden, die nicht dem Standard entsprechen. Wenn Sie eine Bibliothek installieren oder herunterladen müssen , um sie getrennt von der Ersteinrichtung zu verwenden, ist dies nicht zulässig

Objekte können eine negative Masse und einen negativen Wert haben (dh -1, -1).

Optimale Antworten erforderlich

Gewinnen

Der kürzeste Code gewinnt

Negative Masse und Wert?

Dies ist ein wesentlicher Bestandteil dieser Herausforderung. Nehmen wir an, Sie haben ein Objekt mit Gegenständen (Masse, Wert) wie [4,3],[-1,-1]und eine Tasche mit einer Kapazität von 15. Sie könnten 3 der ersten setzen und 9 Punkte erzielen oder 4 der ersten und eine der -1, -1 Objekt für eine Punktzahl von 11.

code-golf optimization Christopher
quelle
Sandkasten
Christopher
Können wir annehmen, dass kein Objekt eine nicht positive Masse hat?
HyperNeutrino
@ HyperNeutrino eine Sekunde entfernen für Änderungen
Christopher
2
Können wir annehmen, dass alles eine ganze Zahl ist? Müssen wir uns auch mit Fällen wie [[2, 1], [-1, -1]] befassen, in denen der Gesamtwert beliebig groß gemacht werden kann?
5
Der Titel ist irreführend. Aufgrund negativer Gewichte ist dies nicht das Rucksackproblem, sondern eine Variation des linearen Programmierproblems.
ngn

Antworten:

2

Pyth, 18 Bytes

h.MshMZfghQseMTy*F

Gibt als Liste von [Wert, Gewicht] -Paaren aus. Schrecklich ineffizient, aber es ist NP-vollständig.
Probieren Sie es hier aus

Erläuterung

h.MshMZfghQseMTy*F
               y*FQ  Get all sets with up to <capacity> of each item.
       fghQseMT      Choose the sets whose total weight fits in the bag.
 .MshMZ              Choose those with the highest value.
h                    Take the first.

quelle