Während Standard-Rucksack-Problem durch dynamische Programmierung gelöst werden kann, versuche ich, das Problem ein wenig zu verdrehen, um mein Konzept zu klären, aber ich fand es vielleicht härter als ich dachte.
Ursprüngliches Rucksackproblem besteht darin, dass bei einem Rucksack mit der Größe W und einer Liste mit Artikeln mit dem Gewicht w[i] und einem Wert v[i] die Teilmenge der Artikel gefunden wird, die in den Rucksack mit dem höchsten Gesamtwert passen .
Nach meinem Verständnis kann dies mit dynamischer Programmierung von O(Wn) erfolgen, wobei n die Anzahl der Elemente ist.
Wenn ich jetzt versuche, m constrains hinzuzufügen, ist jeder von ihnen ein Paar von Gegenständen, die nur gegenseitig ausgewählt werden können (dh wenn es eine Beschränkung von Gegenstand A und Gegenstand B gibt, dann kann ich nur einen annehmen) von ihnen, aber nicht beide)
Kann dieses Problem unter diesen Bedingungen durch dynamische Programmierung in O(Wn) gelöst werden?
Annahme : Jedes Element ist in mindestens einer Einschränkung enthalten.
Für das übliche Knapsack-Problem ist die optimale Unterstruktur, die das Problem aufweist, die folgende:
Für jeden Artikel kann es zwei Fälle geben:
1. Der Artikel ist in der Lösung enthalten
2. Der Artikel nicht in der Lösung enthalten.
Daher ist die optimale Lösung für n -Elemente gegeben durch max der folgenden zwei Werte.
1. Maximaler Wert, der von n-1 -Elementen und W Weight erhalten wird.
2. v_n + maximaler Wert, der von n-1 items und W-w_n weight erhalten wird.
Wenn nun die Einschränkung hinzugefügt wird, dass entweder n th oder (n-1) th item in der Lösung existieren kann, dann ist die optimale Lösung für n items durch max der folgenden drei Werte gegeben.
1. Maximaler Wert, der von n-2 -Elementen und W Weight erhalten wird.
2. v_n + maximaler Wert, der von n-2 items und W-w_n weight erhalten wird.
3. v_(n-1) + maximaler Wert, der von n-2 items und W-w_(n-1) weight erhalten wird.
Also behandeln wir jedes Elementpaar in der Abhängigkeit als ein einzelnes Element und führen den dynamischen Programmieralgorithmus in O(Wn) time aus.
Tags und Links algorithm dynamic-programming