Rucksackproblem mit zwei Schranken?

[microkernel]

Moin

Ich soll für die Schule ein Programm zur Lösung des Rucksacksproblem schreiben. Gegeben sind mir eine Menge von Objekten mit einem Volumen, einen Gewicht und einen Wert. In der Aufgabe steht, dass der Rucksackträger nur eine maximale Last von L_m tragen kann und dass der Rucksack ein maximales Volumen V_m hat. Nun soll ich ein Optimierungsverfahren implementieren, welches für eine geb. Menge von Objekten die Teilmenge findet, welches den höchsten Profit erreicht.
Nun bin ich gerade etwas am grübeln, da ich das Rucksackproblem nur mit einer Gewichtsschranke kenne und nicht gleich zwei Schranken (Volumen- und Gewichtsschranke). Kennt jemand ein geeignetes Lösungsverfahren, welches ich anwenden könnte?

Lg
microkernel

P.S. Der Betrag der Menge von Objekten liegt ungefähr bei 30 bis 40. Alle Möglichkeiten ( 2** 40 ) zu durchlaufen, wäre demnach nicht wirklich effizient

[lunar]

@microkernel Effizient kannst Du die beste Lösung gar nicht finden. Ohnehin kann es mehrere optimale Lösungen geben. Du kannst allenfalls heuristische Verfahren verwenden, um verhältnismäßig effizient eine verhältnismäßig gute – aber nicht notwendigerweise die beste – Lösung zu finden. Diese Algorithmen sind allerdings wesentlich komplexer als ein einfacher Backtracking-Ansatz.

Ich kann mir nicht vorstellen, dass man an einer Schule eine solche Aufgabe stellt, ohne weitere Hinweise zu geben, denn die Komplexität und der theoretische Hintergrund dieses Problems übersteigt eigentlich das, was ich an einer normale Schule (sprich weder FH noch Universität) erwarten würde.

[microkernel]

Mir ist schon klar, dass ich hierbei ein Optimierungsverfahren benötige. (Ist ja klar bei einer Komplexität von O(2^n)) Des weiteren haben wir NP Vollständigkeit, die Liste der 21 NP-Vollständigen Problemen und im Fokus auch das Rucksackproblem im Unterricht behandelt. Ich hab ja auch nur nach der wissenschaftlichen Bezeichnung dieser "Erweiterung" des Rucksackproblems gesucht. Fündig geworden bin ich jetzt übrigens hier: http://rosettacode.org/wiki/Knapsack_Problem/Python Man bezeichnet das als Multiply-Constrained Knapsack Problem oder Multi-Dimensional Knapsack Problem
(Doch, das wird tatsächlich von uns verlangt. Aber immerhin nur im Leistungskurs des Abiturjahrgangs )