Ein Packalgorithmus ... Art

Question

eine Reihe von Positionen gegeben, von denen jede eine value und cost hat, Was ist der beste Algorithmus die Elemente bestimmen, die erforderlich einen minimalen Wert zu minimalen Kosten zu erreichen zum Beispiel:

Item: Value -> Cost
-------------------
A     20   -> 11
B     7    -> 5
C     1    -> 2

MinValue = 30
naive solution: A + B + C + C + C. Value: 30, Cost 22
best option: A + B + B.            Value: 34, Cost 21

Beachten Sie, dass der Gesamtwert:. Kostenquote am Ende keine Rolle spielt (A + A Sie Geld mit dem besten Preis geben würde, aber A + B + B ist eine billigere Option, die den Minimalwert trifft)

Answer 1

Dies ist das Ranzen Problem. (Das heißt, die Entscheidung Version dieses Problems ist die gleiche wie die Entscheidungsversion des Knapsackproblems, obwohl die Optimierung Version des Knapsackproblems in der Regel anders angegeben.) Es ist NP-hart (die kein Algorithmus bedeutet, bekannt ist, dass ist Polynom in der „Größe“ - Anzahl der Bits - im Eingang). Aber wenn Ihre Zahlen klein sind (den größten „Wert“ in der Eingabe, sagt, die Kosten sind nicht wichtig), dann gibt es eine einfache dynamische Programmierlösung

.

Lassen Sie am besten [v] werden die minimalen Kosten einen Wert von (genau) v erhalten dann können Sie die Werte am besten [] für alle v berechnen, durch (Initialisieren alle am besten [v] bis ins Unendliche und).

best[0] = 0
best[v] = min_(items i){cost[i] + best[v-value[i]]}

Dann am besten aussehen [v] für Werte bis zu dem Minimum Sie wollen und den größten Wert; die kleinst die geben Ihnen die Kosten.

Wenn Sie die aktuellen Artikel wollen (und nicht nur die minimal Kosten), können Sie entweder zusätzliche Daten pflegen, oder schauen Sie einfach durch die Anordnung der besten [] s und folgern daraus.

Answer 2

Dieses Problem wird als ganzzahlige lineare Programmierung bekannt. Es ist NP-hart. Doch für kleine Probleme wie Ihr Beispiel ist es trivial eine schnelle paar Zeilen Code einfach Brute-Force all niedrigen Kombinationen von Kaufentscheidungen zu treffen.

NP-harddoesn't bedeutet unmöglich oder sogar teuer, es bedeutet, dass Ihr Problem mit größerem Maßstab Problemen zu lösen schnell langsamer wird. In Ihrem Fall mit nur drei Elementen, können Sie dies in wenigen Mikrosekunden lösen.

Für die genaue Frage, was ist der beste Algorithmus im Allgemeinen .. gibt es ganze Lehrbücher darauf. Ein guter Start ist gute alte Wikipedia.

Answer 3

Bearbeiten Diese Antwort wegen des Seins sachlich falsch unkenntlich gemacht wird. Im Anschluss an die Beratung in dieser wird nur Sie Schaden zufügen.

Dies ist nicht wirklich das Knapsackproblems, weil es davon ausgeht, dass Sie nicht mehr Einzelteile verpacken können, als es Platz für in irgendeinem Behälter ist. In Ihrem Fall, dass Sie die günstigste Kombination finden wollen, die den Raum füllen werden, unter Berücksichtigung der Tatsache, dass Überlauf auftreten kann.

Meine Lösung, die ich nicht weiß, ist die optimale, aber es sollte ziemlich nah dran sein, würde für jedes Element der Kosten-Nutzen-Verhältnis, finden Sie das Element mit der höchsten Kosten-Nutzen-und füllen Sie die Struktur mit diesem Element zu berechnen, bis es gibt keinen Platz für ein weiteres Einzelteil. Dann würde ich prüfen, um zu sehen, ob es eine Kombination mit allen anderen verfügbaren Elemente war, die den verfügbaren Platz für weniger als die Kosten für eine der billigsten Produkte füllen könnte und dann, wenn eine solche Lösung vorhanden sind, verwenden Sie diese Kombination sonst eine Verwendung mehr die billigsten Produkte.

Amenddum Dies kann NP-vollständig sein eigentlich auch, aber ich bin noch nicht sicher. Auf jeden Fall für alle praktischen Zwecke sollte diese Variante wesentlich schneller als die naive Lösung.