home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / programm / 3329 < prev    next >
Encoding:
Text File  |  1992-12-18  |  1.3 KB  |  37 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cs.utexas.edu!torn!newshost.uwo.ca!phobos.sscl.uwo.ca!john
  3. From: john@phobos.sscl.uwo.ca (John Tucker)
  4. Subject: Knapsack problem??
  5. Organization: University of Western Ontario
  6. Date: Thu, 17 Dec 1992 21:02:41 GMT
  7. Message-ID: <1992Dec17.210241.8948@julian.uwo.ca>
  8. Summary: C code for knapsack algorithm needed 
  9. Sender: news@julian.uwo.ca (USENET News System)
  10. Nntp-Posting-Host: phobos.sscl.uwo.ca
  11. Lines: 24
  12.  
  13. Here is my problem:
  14.     I have N items with an associated cost of Cn. I want to select
  15. the best subset of these items where TotalCost-Tolerance < Sum(Cn) <
  16. TotalCost.
  17.  
  18.     I know it is a form of a knapsack problem, but I can't recollect the
  19. elegant way of coding this. I'm using a brute force algorithm based on
  20. 2^n possible combinations of n objects taken 0..n at a time. This limits
  21. me to a max of 32 items and is slow (micro) to acceptable (DECstation 5000).
  22.  
  23.     I know there is an excellent book (with code), but I can't remember
  24. the name or author ...and its probably already signed out of the library.
  25.  
  26.     So if you have any code (C C++ Pascal Modula-2) which can help me,
  27. or if you know of an ftp site. Please Help!!!
  28.  
  29. E-mail me as :jtucker@uwo.ca
  30.  
  31.  
  32. -- 
  33. --
  34. jtucker@uwo.ca  John Tucker
  35.  
  36. A university is what a college becomes when the faculty loses interest
  37.