home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compress / 4807 < prev    next >
Encoding:
Text File  |  1993-01-26  |  1.1 KB  |  27 lines
  1. Newsgroups: comp.compression
  2. Path: sparky!uunet!rei2!fox
  3. From: fox@rei.com (Fuzzy Fox)
  4. Subject: Re: zipsplit with pkzip204c Was: Re: Unix release? (Was etc.
  5. Message-ID: <1993Jan26.044940.6569@rei.com>
  6. Date: Tue, 26 Jan 1993 04:49:40 GMT
  7. References: <1993Jan14.051725.19618@ucsu.Colorado.EDU> <Jan19.211317.17236@halcon.dpi.udec.cl> <1jk4c1INN9fu@gap.caltech.edu> <9cl333-@rpi.edu>
  8. Organization: Recognition Equipment, Inc.
  9. Lines: 16
  10.  
  11. sigma@degas.ipl.rpi.edu (Kevin Martin) writes:
  12.  
  13. >This is what's called the Knapsack Problem.  It's NP-complete, but since
  14. >your knapsack is usually relatively small compared to the total size of the
  15. >files, an early-out algorithm which avoids combinations which will
  16. >obviously not fit actually has to check very few combinations.
  17.  
  18. Where can I find a write-up or description of an algorithm which solves
  19. the Knapsack Problem?  I have been unable to locate such a description
  20. (or even source code).
  21.  
  22. -- 
  23. #ifdef TRUE        | Fuzzy Fox (a.k.a. David DeSimone)       fuzzy@netcom.com
  24. #define  TRUE   0  |
  25. #define  FALSE  1  |         "S-O-C-K-S ?   Wow, Spanish *is* easy!!"
  26. #endif             |
  27.