Ich studiere dynamische Programmierung und suche nach Lösungen für das folgende Problem, das hier zu finden isthttp://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf:

Sie erhalten ein rechteckiges Stück Stoff mit den Maßen X x Y, wobei X und Y positive ganze Zahlen sind, und eine Liste von n Produkten, die mit dem Stoff hergestellt werden können. Für jedes Produkt i in [1, n] wissen Sie, dass ein Rechteck aus Stoff mit den Maßen ai bis bi benötigt wird und dass der endgültige Verkaufspreis des Produkts ci ist. Angenommen, ai, bi und ci sind alle positive ganze Zahlen. Sie haben eine Maschine, die jedes rechteckige Stück Stoff horizontal oder vertikal in zwei Teile schneiden kann. Entwerfen Sie einen Algorithmus, der die beste Strategie zum Schneiden eines Stücks Stoff X x Y findet, sodass die aus den resultierenden Stücken hergestellten Produkte die maximale Summe der Verkaufspreise ergeben. Es steht Ihnen frei, so viele Kopien eines bestimmten Produkts zu erstellen, wie Sie möchten, oder auf Wunsch auch keine. (Aus Algorithmen von Dasgupta, Papadimitriou und Vazirani.)

Es scheint, dass wir eine Art zweidimensionales Rucksackproblem haben, aber ich denke, dass es möglich sein könnte, es einfach mit dem herkömmlichen Rucksackalgorithmus zu lösen, indem man die Gewichte als Flächen der Rechtecke betrachtet. Scheint dies ein vernünftiger Ansatz zu sein?

Dies ist eine Programmieraufgabe für einen Kurs, den ich besuche. Bitte füge nur konzeptionelle Diskussionen und / oder Pseudocodes hinzu, um Ideen zu veranschaulichen.