Estou estudando programação dinâmica e estou procurando resolver o seguinte problema, que pode ser encontrado aquihttp://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf:

Você recebe um pedaço de tecido retangular com as dimensões X por Y, onde X e Y são inteiros positivos e uma lista de n produtos que podem ser feitos usando o pano. Para cada produto i em [1, n] você sabe que um retângulo de tecido de dimensões ai por bi é necessário e que o preço final de venda do produto é ci. Suponha que ai, bi e ci sejam todos inteiros positivos. Você tem uma máquina que pode cortar qualquer pedaço retangular de pano em duas partes, horizontalmente ou verticalmente. Projete um algoritmo que encontre a melhor estratégia para cortar um pedaço de pano X, de modo que os produtos feitos com as peças resultantes forneçam a soma máxima dos preços de venda. Você é livre para fazer quantas cópias de um determinado produto desejar, ou nenhuma, se desejar. (De Algorithms por Dasgupta, Papadimitriou e Vazirani.)

Parece que temos uma espécie de problema de mochila bidimensional, mas acho que é possível resolvê-lo apenas com o algoritmo de mochila tradicional, considerando os pesos como as áreas dos retângulos. Isso parece uma abordagem razoável?

Esta é uma tarefa de programação para um curso que estou cursando, por isso inclua apenas discussões conceituais e / ou pseudo-códigos para ilustrar idéias.