Kann ich dynamische Programmierung verwenden, um dies zu lösen?

Question

Ich habe sehr wenig Erfahrung mit dynamischer Programmierung. Ich benutzte es, um ein DNA-Alignment-Problem, ein grundlegendes Rucksackproblem und ein einfaches Wegfindungsproblem zu lösen. Ich habe verstanden, wie sie funktioniert haben, aber ich fühle mich noch nicht mit ihr verbunden.

Ich habe ein Problem, das mich an 0-1 dynamische Programmierung erinnert, aber die Unterschiede haben mich abgeworfen, und ich bin mir nicht sicher, ob ich diese Technik noch verwenden kann, oder wenn ich mich für einen rekursiven Ansatz begnüge .

Nehmen wir an, ich habe eine Liste von Artikeln mit unterschiedlichen Werten, Gewichten und Kosten. Es kann mehr als einen von jedem Gegenstand geben.

Lassen Sie uns sagen, ich muss eine Kombination dieser Elemente wählen, die am wertvollsten ist, aber innerhalb der Grenzen von Gewicht und Kosten bleibt. Bisher habe ich das Rucksackproblem mit 2 Einschränkungen beschrieben. Aber hier ist der Unterschied:

Der Wert eines ausgewählten Elements ändert sich je nachdem, wie viele von ihnen ich in der Kombination habe.

Sagen wir, dass jedem Element eine Funktion zugeordnet ist, die mir sagt, was eine Gruppe dieser Elemente für mich wert ist. Es ist eine grundlegende lineare Funktion, wie value_of_item = -3 (Menge dieses Artikels) + 50

Also wenn ich 1 eines Artikels in einer Combo habe, dann ist es Wert für mich ist 47. Wenn ich 2 hatte sie, dann sind sie mir nur 44 wert.

Wenn ich eine dynamische Programmierungstabelle dafür verwende, dann müsste ich für jede Zelle zurückgehen, um zu sehen, ob dieses Element bereits in der aktuellen Kombination ist, was DP sinnlos macht. Aber vielleicht gibt es eine Möglichkeit, das Problem neu zu definieren, damit ich DP nutzen kann.

Hoffentlich machte das Sinn.

Die Alternative ist, jede Kombination von Elementen zu generieren, innerhalb der Grenzen von Kosten und Gewicht, den Wert von jeder Kombination, wählen Sie die wertvollste Kombination. Für eine Liste von 1000 Artikeln sogar, das wird eine teure Suche sein, und es ist etwas, das ich immer wieder berechnen würde. Ich würde gerne einen Weg finden, die Vorteile von DP zu nutzen.

Answer 1

Wenn Ihre Funktionen der Form sind

value(x, count) = base(x) - factor(x) * count, factor(x) > 0, 

dann können Sie das Problem zu Standard Ranzen reduzieren, indem Sie die Elemente aufteilen:

x -> x_1 to x_max_count 
value_new(x_i) = value(x, i) 
weight(x_i) = weight(x) 

Nun überprüfen Sie einfach, dass keine optimale Lösung für das neue Problem verwendet einige Artikel x_j, ohne jede x_i mit i < j zu verwenden.

Beweis durch Widerspruch: Angenommen, es gibt so eine optimale Lösung S und es verwendet x_j, aber nicht x_i, j> i. Dann gibt es eine alternative Lösung S ', die x_i anstelle von x_j verwendet. Da j> i,

und daher S 'hat einen höheren Wert als S und wir haben einen Widerspruch erreicht.

Weiterhin können wir factor(x) = 0 zulassen, dies entspricht einem Standard-Rucksackartikel.

jedoch, wenn es eine Beschränkung der Form

value(x, count) = base(x) + factor(x) * count 

wo factor(x) einen willkürlichen Wert ist, die Lösung oben nicht mehr arbeitet, weil der letzte Punkt derjenige mit dem größten Wert wäre. Vielleicht erlaubt Ihnen eine ausgeklügelte Modifikation von DP, solche Einschränkungen zu verwenden, aber ich sehe keine Modifikationen des Problems selbst, um DP sofort zu verwenden.

Einige Untersuchungen in diesem Thema (mehr allgemein):

• http://dept.cs.williams.edu/~heeringa/publications/knapsack.pdf
• http://clweb.csa.iisc.ernet.in/vsuresh/Kamesh-PLKP.pdf