Ordnung schnellen ÜberblickMögliche Kombination von Rucksackproblem und?
Ich habe in den Knapsackproblems sah
http://en.wikipedia.org/wiki/Knapsack_problem
und ich weiß, es ist, was ich für mein Projekt benötigen, aber der komplizierteste Teil meines Projektes wäre, dass ich mehrere brauchen Säcke in einem Hauptsack.
Der große Rucksack, der alle "Taschen" enthält, kann nur x Menge an "Taschen" tragen (sagen wir 9 für Beispiel). Jede Tasche hat unterschiedliche Werte;
- Gewicht
- Kosten
- Größe
- Kapazität
und so weiter, all diese Werte sind ganze Zahlen. Nehmen wir an von 0-100.
Der inneren Tasche wird auch ein Typ zugewiesen, und es kann nur einen dieser Art innerhalb der äußeren Tasche geben, obwohl der Programmeingabe ein Vielfaches des gleichen Typs gegeben wird.
Ich muss ein maximales Gewicht zuweisen, dass die Haupttasche halten kann, und alle anderen Eigenschaften der kleineren Taschen müssen nach gewichteten Werten gruppiert werden.
Beispiel
Außentasche:
- Kann halten 9 kleinere Taschen
- Gewicht nicht mehr als 98 [Geben oder 5 auf beiden Seiten nehmen]
- muss ein jeder halten type, Kann nur jeweils einen Typ gleichzeitig halten.
Innere Taschen:
- Kosten, bei 100% Gewichteter
- Größe, bei 67% Gewichteter
- Kapazität bei 44% Gewichteter
Das Programm wird eine Eingabe von mehreren Taschen gegeben, und dann müssen Kombinationen von kleineren Taschen erarbeiten, um in die la zu gehen In Abhängigkeit von der Eingabe wird es mehrere Lösungen geben, und das Programm würde die besten Lösungen für mich ausgeben.
Ich frage mich, was Sie denken, der beste Weg für mich, dies zu erreichen wäre.
Ich werde es in Java oder C# programmieren. Ich würde es gerne in PHP programmieren, aber ich fürchte, der Algorithmus wäre für Webserver sehr ineffizient.
Vielen Dank für jede Hilfe, die Sie
-Zack
So kümmert es dich nicht wirklich um die inneren Taschen füllen? Sie möchten nur Gegenstände (innere Taschen) in eine Tasche (äußere Tasche) mit der zusätzlichen Einschränkung, dass die Tasche (äußere Tasche) nicht mehrere Gegenstände (innere Taschen) des gleichen Typs enthalten kann. Recht? –
Müssen Sie alle Innenbeutel in Außenbeutel packen oder nur einen Außenbeutel füllen - also Binpacking oder Knapsack? –
Ja, und die Einschränkung, dass die äußere Tasche nur so viel Gewicht enthalten kann, habe ich weiter in diese Art von Problem untersucht und es scheint entweder bin Verpackung oder Rucksack, oder beides. In Zukunft muss ich vielleicht die inneren Taschen füllen, aber ich möchte mich zuerst auf dieses Problem konzentrieren. –