Ich denke, dass dies eine Variation des mehrfachen Rucksackproblems sein könnte (oder vielleicht sogar darauf reduziert werden könnte), aber ich bin mir nicht sicher. Hier ist das Problem:Variation auf Knapsack-Algorithmus
Sie haben eine Reihe von Elementen mit bekannten Werten und Gewichten. Sie haben auch eine Reihe von Rucksäcken, und jeder Rucksack kann eine feste Anzahl von Gegenständen (verschiedene Rucksäcke können in der Lage sein, eine unterschiedliche Anzahl von Gegenständen zu halten). Maximiere den Gesamtwert von Gegenständen in Rucksäcken, während du unter einem bestimmten Gewicht bleibst.
Beachten Sie, dass die einzelnen Rucksäcke keine Gewichtsbeschränkung haben. Jeder Rucksack hat nur eine Beschränkung "Anzahl der Items, die er enthalten kann". Die einzige andere Einschränkung ist das Gesamtgewicht der Artikel.
Irgendwelche Ideen ?? (außer roher Gewalt natürlich). Danke im Voraus! :)
EDIT: eine wichtige Einschränkung I umfassen vergessen zu:
Items können nicht unbedingt in jede Tasche genommen werden. Im Wesentlichen wird ihr Wert Null, wenn sie in eine Tasche gesteckt werden, mit der sie nicht kompatibel sind. Sie können sich einen allgemeinen Fall vorstellen, in dem jeder Gegenstand einen Wert hat, der von seinem Beutel abhängt, aber für meinen Fall ist sein Wert entweder 0 oder sein normaler Wert, abhängig vom Beutel.
Ist das Hausaufgaben? Wenn dies der Fall ist, sollten wir das Tag als solches markieren. Was hast du probiert? –
Uh - Hausaufgaben? :) Wahrscheinlich werde ich hier etwas Hass bekommen. – SinisterRainbow
Das ist 'Knapsack' wenn du die verschiedenen Rucksäcke als einen einzigen Knapsack behandelst ist es genauso. Es gibt viele Möglichkeiten, Knapsack zu approximieren. Ich bin sicher, dass Sie sie finden können, wenn Sie eine Google-Suche machen. – twain249