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

So you start with a X * Y rectangle. Say the optimal solution involves making a vertical (or horizontal) cut, then you have two new rectangles with dimensions X * Y1 and X * Y2 with Y1 + Y2 = Y. Since you want to maximize your profit, you need to maximize the profit on these new rectangles (optimal substructure). So your initial recursion goes as follows: f(X, Y) = max(f(X, Y1) + f(X, Y2), f(X1, Y) + f(X2, Y)) for all posible values of X1, X2 (horizontal cut) and Y1, Y2 (vertical cut).

Now the question is when do I actually decide to make a product ? You can decide to make a product when one of its dimensions equals one of the dimensions of your current rectangle (why ? Because if this doesn't hold, and the optimal solution includes making this product, then sooner or later you will need to make a vertical (or horizontal) cut and this case is already handled in the initial recursion), so you make the appropriate cut and you have a new rectangle X * Y1 (or X1 * Y), depending on the cut you made to obtain the product), in this case the recursion becomes f(X, Y) = cost of product + f(X1, Y).

The solution of the original problem is f(X, Y). The running time of this dp solution would be O(X * Y * (X + Y + number of available products)): you have X * Y possible rectangles, for each of these you try every possible cut (X + Y) and you try to make one of the available products out of this rectangle.

Also, check out this similar problem: Sharing Chocolate from the 2010 ICPC World Finals.

Answer 2

I think you should focus on the fact that the machine cuts the cloth into two pieces. What can fit in each of those two pieces? Consider the following:

+-------------+-------------------+
|             |       Piece B     |
|             |                   |
|  Piece A    +----------+--------+
|             |          |        |
|             |          |        |
|             |          | Piece  |
+-------------+----------+   C    |
|                        |        |
|         Piece D        |        |
+------------------------+--------+

These four fit in the cloth, but not in a way that's possible to achieve with three cuts. (Possibly a different arrangement would allow that with these particular pieces; think of this as a conceptual diagram, not to scale. My ascii art skills are limited today.)

Focussing on "where is the cut" should give you the dynamic programming solution. Good luck.