home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / compress / 4859 < prev    next >
Encoding:
Text File  |  1993-01-29  |  1.6 KB  |  43 lines
  1. Newsgroups: comp.compression
  2. From: fred@genesis.demon.co.uk (Lawrence Kirby)
  3. Path: sparky!uunet!spool.mu.edu!agate!doc.ic.ac.uk!pipex!ibmpcug!demon!genesis.demon.co.uk!fred
  4. Subject: Re: Unix release? (Was etc. 
  5. Distribution: world
  6. References: <C1EArp.KL@unix.amherst.edu>
  7. Organization: BT
  8. X-Mailer: Simple NEWS 1.90 (ka9q DIS 1.19)
  9. Lines: 29
  10. Date: Thu, 28 Jan 1993 18:40:51 +0000
  11. Message-ID: <728246451snz@genesis.demon.co.uk>
  12. Sender: usenet@demon.co.uk
  13.  
  14. In article <C1EArp.KL@unix.amherst.edu> djweisbe@unix.amherst.edu writes:
  15.  
  16. >Lawrence Kirby (fred@genesis.demon.co.uk) wrote:
  17. >: 
  18. >: The knapsack problem deals with a single knapsack (i.e. disk) and is NOT
  19. >: NP-complete. It's a common example of dynamic programming where the optimal
  20. >
  21. >The Knapsack problem sure is NP complete.  I believe the following
  22. >explanation is correct, if simple (check in comp.theory, though):
  23. >
  24. >There is an algorithm which is linear in N, the number of items, but
  25. >the specification of N is of length proportional to log N, so the
  26. >running time is actually exponential in the length of the input.
  27.  
  28. The input data to the problem isn't the number of items, it is in general a list
  29. of the items. The size of this input data will be proportional to N, not log N.
  30. The problem isn't even be exponential on the size of the knapsack since the
  31. size is constrained by the total size of the items available.
  32.  
  33. >Just a humble undergrad,
  34. >  David
  35. >
  36.  
  37. Happy days!
  38.  
  39. -----------------------------------------
  40. Lawrence Kirby | fred@genesis.demon.co.uk
  41. Wilts, England | 70734.126@compuserve.com
  42. -----------------------------------------
  43.