Estoy estudiando programación dinámica y estoy buscando resolver el siguiente problema, que se puede encontrar aquíhttp://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf:

Se le entrega una pieza de tela rectangular con las dimensiones X por Y, donde X e Y son enteros positivos, y una lista de n productos que se pueden hacer con la tela. Para cada producto i en [1, n] usted sabe que se necesita un rectángulo de tela de dimensiones ai por bi y que el precio de venta final del producto es ci. Supongamos que ai, bi y ci son todos enteros positivos. Tiene una máquina que puede cortar cualquier pieza de tela rectangular en dos piezas, ya sea horizontal o verticalmente. Diseñe un algoritmo que encuentre la mejor estrategia para cortar una pieza de tela X por Y para que los productos hechos de las piezas resultantes den la suma máxima de los precios de venta. Usted es libre de hacer tantas copias de un producto determinado como desee, o ninguna si lo desea. (De los algoritmos de Dasgupta, Papadimitriou y Vazirani).

Parece que tenemos una especie de problema de mochila bidimensional, pero creo que es posible resolverlo simplemente con el algoritmo de mochila tradicional considerando los pesos como las áreas de los rectángulos. ¿Parece esto un enfoque razonable?

Esta es una asignación de programación para un curso que estoy tomando, así que solo incluya discusión conceptual y / o pseudo-código para ilustrar ideas.