home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / programm / 3343 < prev    next >
Encoding:
Internet Message Format  |  1992-12-22  |  1.5 KB
  1. Path: sparky!uunet!olivea!spool.mu.edu!yale.edu!yale!gumby!destroyer!ncar!noao!amethyst!organpipe.uug.arizona.edu!news
  2. From: dave@cs.arizona.edu (Dave Schaumann)
  3. Newsgroups: comp.programming
  4. Subject: Re: Knapsack problem??
  5. Message-ID: <1992Dec21.191234.17727@organpipe.uug.arizona.edu>
  6. Date: 21 Dec 92 19:12:34 GMT
  7. References: <1992Dec17.210241.8948@julian.uwo.ca>
  8. Sender: news@organpipe.uug.arizona.edu
  9. Reply-To: dave@cs.arizona.edu (Dave Schaumann)
  10. Organization: University of Arizona
  11. Lines: 24
  12. In-Reply-To: john@phobos.sscl.uwo.ca (John Tucker)
  13.  
  14. In article <1992Dec17.210241.8948@julian.uwo.ca>, john@phobos (John Tucker) writes:
  15. >    I have N items with an associated cost of Cn. I want to select
  16. >the best subset of these items where TotalCost-Tolerance < Sum(Cn) <
  17. >TotalCost.
  18. >
  19. >    I know it is a form of a knapsack problem
  20.  
  21. Yup.
  22.  
  23. >but I can't recollect the
  24. >elegant way of coding this. I'm using a brute force algorithm based on
  25. >2^n possible combinations of n objects taken 0..n at a time. This limits
  26. >me to a max of 32 items and is slow (micro) to acceptable (DECstation 5000).
  27.  
  28. I hate to break this to you, but the Knapsack problem is NP-complete.
  29. That means if someone does find a polynomial-time algorithm to solve it,
  30. they'll gain fame (well, at least within CS circles) as well as the
  31. satisfaction of having solved a long-standing open question in CS theory.
  32.  
  33. On the other hand, there could very well be a polynomial time algorithm
  34. for a special case which is useful for your purposes.
  35.  
  36. -- 
  37. Dave Schaumann            dave@cs.arizona.edu
  38.