Dynamic Programming and Knapsack Application?

Question

Im studying dynamic programming and am looking to solve the following problem, which can be found here http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf: You are given a rectangular piece of cloth with dimensions X by Y, where X and Y are positive integers, and a list of n products that can be made using the cloth. For each product i in [1,n] you know that a rectangle of cloth of dimensions ai by bi is needed and that the final selling price of the product is ci. Assume that ai, bi, and ci are all positive integers. You have a machine that can cut any rectangular piece of cloth into two pieces either horizontally or vertically. Design an algorithm that finds the best strategy for cutting an X by Y piece of cloth so that the products made from the resulting pieces give the maximum sum of selling prices. You are free to make as many copies of a given product as you wish, or none if desired. (From Algorithms by Dasgupta, Papadimitriou, and Vazirani.) It seems we have a sort of 2-dimensional knapsack problem, but I'm thinking it may be possible to just solve it with the traditional knapsack algorithm by considering the weights as the areas of the rectangles. Does this seem like a reasonable approach? This is a programming assignment for a course I'm taking so please only include conceptual discussion and/or pseudo-code to illustrate ideas.

Answer 1

I propose to solve this problem by recursion as follows. I assume that the cloth is such that a product can be oriented either way. I observe that after a cut, we have two pieces of cloth. So we make a list of the side lengths of the products that fit in the piece, We consider a vertical cut for each side length and a horizontal cut for each side length, then apply the same algorithm to each of the two resulting pieces. If that list is empty, the side is considered scrap with no value and we return a profit of 0.0 without further recursion. If a cut results in one piece that matches a single product and a second piece that is scrap, we return the value of that product without further recursion. As we recurse through the various cuts, we keep a stack of the cuts we used to get there. When we have considered all possible cuts, we pick the sequence with the greatest profit.

It is probably true that in some cases there is a place to cut that is not at a product side length that would be better. So It might be better to make a list of lengths composed of one, two, or more pieces side by side as long as the sum is less than the length of the side being considered.

I would note that the multiplicity of this solution grows rapidly as the size of the initial sheet grows relative to the size of the products. However for any given cut, the multiplicity for the resulting two pieces is much reduced, so the search is wide but not very deep.

I would also note that this approach is not limited to the two-dimensional problem. It could be applied to a single dimension and also to more than two dimensions. An approach to a proof would be to prove it for one dimension, then assuming it is true for n dimensions, prove it is true for n+1 dimensions.