Question

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. How can i prove that the recursion is exponential and that dynamic programming is polynomial

Answer 1

The proof that recursion is exponential and that dynamic programming is polynomial is given by the formula;

P(x,y) = max{

P(x,y)

max (1 <= h <= X) { P[h, Y] + P(X - h, Y) }

max (1 <= v <= Y) { P[X, v] + P[X, Y - v] }

}

To prove that the recursion is exponential and that dynamic programming is polynomial. we will do so as follows;

Let us first have the assumption that the cloth is in such a manner that  either way, a product can be oriented. This implies that that after a cut, we will now have two pieces of cloth.

Now, we will make a list of the side lengths of the products that can fit in the piece after which we will consider a vertical cut for each of the side length as well as a horizontal cut for each of the side length, then we apply the same algorithm to each of the two resulting pieces.  

Thus, after the point above, it is likely true that in some instances, there may be a place to cut that is not at a product side length. However, It might be better for us to make a list of lengths composed of one or more pieces side by side as long as the sum is less than the length of the side being considered.

 

Lastly, we would note that this recursive approach is not limited to just two -dimensional problems as It could also be applied to a single or more than two dimensions. A useful 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.

Thus;

P(x,y) = max{

P(x,y)

max (1 <= h <= X) { P[h, Y] + P(X - h, Y) }

max (1 <= v <= Y) { P[X, v] + P[X, Y - v] }

}

Read more at; brainly.com/question/11665190