Using dynamic programming and a knapsack

Question

I am studying dynamic programming and want 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 fabric with sizes X to Y, where X and Y are positive integers, as well as a list of n products that can be made using fabric. For each product, I in [1, n] know that you need a rectangle of fabric ai by bi in size and the final selling price of the product is ci. Suppose that ai, bi, and ci are positive integers. You have a machine that can cut any rectangular piece of fabric into two parts horizontally or vertically. Create an algorithm that finds the best strategy for cutting a piece of fabric X into Y so that products made from the resulting products give the maximum amount of selling prices. You can make as many copies of this product as you want, or not if you want. (From the algorithms of Dasgupt, Papadimitriou, and Wazirani.)

It seems that we have a kind of two-dimensional problem with a backpack, but I think that we can simply solve it using the traditional knapsack algorithm, considering the weights as regions of rectangles. Does this sound like a reasonable approach?

This is a programming purpose for a course that I am taking, so please use only a conceptual discussion and / or pseudo-code to illustrate ideas.

Answer 1

So you start with the rectangle X * Y Let's say the optimal solution involves creating a vertical (or horizontal) section, then you have two new rectangles with dimensions X * Y1 and X * Y2 using Y1 + Y2 = Y Since you want to maximize your profit, you need to maximize profit on these new rectangles (optimal substructure). So, your initial recursion is as follows: f(X, Y) = max(f(X, Y1) + f(X, Y2), f(X1, Y) + f(X2, Y)) for all possible values X1, X2 (horizontal section) and Y1, Y2 (vertical section).

Now the question is, when do I really decide to make a product? You can decide to make a product when one of its sizes is equal to one of the dimensions of your current rectangle (why? Because if this is not done and the optimal solution involves creating this product, then sooner or later you will need to make a vertical (or horizontal) slice, and this case is already being processed in the initial recursion), so you make the corresponding cut, and you have a new rectangle X * Y1 (or X1 * Y ), depending on the cut you made to get the product), in in this case recursion with becomes f(X, Y) = cost of product + f(X1, Y) .

The solution to the original problem 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 them you can try all possible abbreviations ( X + Y ) , and you are trying to make one of the available products from this rectangle.

Also, check out this similar issue: Chocolate Splitting in the ICPC World 2010 Finals.

Answer 2

Please specify the necessary conditions for a rectangle of size (0, something) or (something, 0) in the Rect () function.

Answer 3

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

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

These four fit into the fabric, but not in the way you can achieve with three cuts. (Perhaps another arrangement would allow this to be done using these specific parts, think of it as a conceptual diagram, not a scale. My ascii art skills are limited today.)

Focusing on where to cut should give you a dynamic programming solution. Good luck.

Answer 4

optimize () {

 Rectangle memo[width][height] optimize(0,0,totalwidth, totalheight, memo) 

}

optimize (x, y, width, height, memo) {

 if memo[width][height] != null return memo[width][height] rect = new Rectangle(width, height, value = 0) for each pattern { //find vertical cut solution leftVerticalRect = optimize (x, y + pattern.height, pattern.width, height-pattern.height,memo) rightVerticalRect = optimize(x + pattern.width, y, width-pattern.width, height) verticalcut = new Cut(x + pattern.width, y, x + pattern.width, y + height) //find horizontal cut solution topHorizontalRect = optimize ( --parameters-- ) bottomHortizonalRect = optimize( --parameters--) horizontalcut = new Cut( --parameters--) //see which solution is more optimal if (leftVerticalRect.val + rightVerticalRect.val > topHorizontalRect.val + bottomHorizontalRect.val) subprobsolution = vertical cut solution else subprobsolution = horizontal cut solution //see if the solution found is greater than previous solutions to this subproblem if (subprobsolution.value + pattern.value > rect.value) { rect.subrect1 = subprobsolutionrect1 rect.subrect2 = subprobsolutionrect2 rect.pattern = pattern rect.cut = subprobsolutioncut rect.value = rect.subrect1.value + rect.subrect2.value + rect.pattern.value } } memo[width][height] = rect return rect 

}