Where is everybody? Only one answer, which hasn't received any upvotes, nor any downvotes. I don't know any way to put this problem back on the radar screen other than posting an answer to it, so here's an extended version of the answer I already posted.
Garey and Johnson, Computers and Intractability, has a list of problems that are known to be NP-complete. Subset Sum is problem SP13 in that list, on page 223 of the book. I quote:
Instance: Finite set $A$, size $s(a)in{bf Z}^+$ for each $ain A$, positive integer $B$.
Question: Is there a set $A'subseteq A$ such that the sum of the sizes of the elements in $A'$ is exactly $B$?
Now let's look at a special case of the current MO question. Suppose that the multiple shapes are rectangles with base 1 and various integer heights, and the (big) rectangular area also has base 1 and integer height B. Suppose that there is an efficient way to determine the best fit of the shapes in the big rectangle (I am reinterpreting the original request for a "formula" as a request for an efficient method). Then you have an efficient way to solve Subset Sum. Namely, apply the alleged efficient best fit method to the data. If it finds a way to completely fill the big rectangle, then it has found a subset summing to $B$, and if it doesn't find a way to completely fill the big rectangle, then it has proved that there is no subset summing to $B$.
It follows that there is no efficient method for finding a best fit in this special case of the original problem, unless P = NP.
No comments:
Post a Comment