2009-04-23 8 views
3

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

+0

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? –

+0

Müssen Sie alle Innenbeutel in Außenbeutel packen oder nur einen Außenbeutel füllen - also Binpacking oder Knapsack? –

+0

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. –

Antwort

2

Okay, gut, Ranzen ist NP-hart, so bin ich ziemlich sicher, dies wird NP-hart als auch (wenn es nicht waren geben kann Sie könnten Rucksack lösen, indem Sie dies mit nur einer äußeren Tasche tun.) Also für eine genau optimale Lösung, werden Sie wahrscheinlich in der Lage sein, nichts zu tun, als alle Kombinationen zu suchen. So ist die Umrisse des Programms, das Sie wollen, wie

und die Laufzeit wird exponentiell sein. Es klingt jedoch so, als könnten Sie eine nahe Lösung mit dynamic programming bekommen.

0

Verwenden Sie Prolog für Ihre logische Programmierung. Es gibt mehrere Implementierungen davon einschließlich P# auf Mono (.NET). Theres ein bisschen eine Lernkurve, aber sobald Sie sich daran gewöhnt haben, ist es so ziemlich in einer Liga für diese Art von Problemlösung.

Hoffe, das hilft. Prost!

Link zu P#

Verwandte Themen