home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / sys / mac / programm / 13897 < prev    next >
Encoding:
Text File  |  1992-08-12  |  1.7 KB  |  39 lines
  1. Newsgroups: comp.sys.mac.programmer
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!haven.umd.edu!ni.umd.edu!zben-mac-ii.umd.edu!user
  3. From: zben@ni.umd.edu (Charles B. Cranston)
  4. Subject: Re: Packing Rects into the smallest possible container
  5. Message-ID: <zben-120892162027@zben-mac-ii.umd.edu>
  6. Followup-To: comp.sys.mac.programmer,comp.sources.wanted
  7. Sender: usenet@ni.umd.edu (USENET News System)
  8. Nntp-Posting-Host: zben-mac-ii.umd.edu
  9. Organization: UM Home for the Terminally Analytical
  10. References: <1992Aug12.013521.28314@cs.ucla.edu>
  11. Date: Wed, 12 Aug 1992 20:26:24 GMT
  12. Lines: 25
  13.  
  14. In article <1992Aug12.013521.28314@cs.ucla.edu>,
  15. tj@kona.cs.ucla.edu (Tom Johnson) wrote:
  16.  
  17. > I have a bunch of rectangular objects, and I would like to pack them into
  18. > the smallest possible rectangular container (we're only dealing with 2
  19. > dimensions here, I'm not concerned with 3d boxes).  How do I do this?
  20. > The objects may all have different sizes. 
  21. > Any suggestions for algorithms? Ideas?
  22.  
  23. This sounds a lot like a two-dimensional version of what has come to be
  24. called "the knapsack problem" in computer science literature.  You might
  25. be able to find some work being done if you use this buzzword.
  26.  
  27. Actually, the knapsack problem is usually explained in terms of fitting
  28. the maximum amount of stuff in a knapsack of known size, i.e., given a
  29. set of integers {I} and a number N find the maximal subset {i} such
  30. that  sum({i}) <= N  or something like that.  In your case it is more
  31. like finding the minimal N which for the one-dimensional case is simply
  32. sum({I}).
  33.  
  34. The knapsack problem is thought to be NP-complete.  In fact, it was one
  35. of the other schemes besides the factoring problem (RSA) considered for
  36. use in public-key encryption algorithms...
  37.  
  38. zben@ni.umd.edu     -KA3ZDF
  39.