home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v941.tgz / icon.v941src.tar / icon.v941src / ipl / progs / knapsack.icn < prev    next >
Text File  |  2000-07-29  |  2KB  |  69 lines
  1. ############################################################################
  2. #
  3. #    File:     knapsack.icn
  4. #
  5. #    Subject:  Program to fill a container
  6. #
  7. #    Author:   Anthony V. Hewitt
  8. #
  9. #    Date:     August 8, 1993
  10. #
  11. ############################################################################
  12. #
  13. #   This file is in the public domain.
  14. #
  15. ############################################################################
  16. #
  17. #    Version:  1.1
  18. #
  19. ############################################################################
  20. #                                                            
  21. # This filter solves a knapsack problem - how to fill a container to
  22. # capacity by inserting items of various volumes. 
  23. #
  24. #  input:       a string of newline-separated volumes
  25. #
  26. #  argument:    the capacity to be filled exactly
  27. #
  28. #  output:      a single solution
  29. #
  30. # It is derived from fillup.icn, which has a bewildering array of
  31. # options to make it applicable to real-world problems.  In 
  32. # contrast, knapsack is merely a demonstration of the underlying 
  33. # algorithm.
  34. #
  35. # The return statement in trynext() greatly improves the efficiency
  36. # by restricting the search to fruitful branches of the search tree.
  37. # While the use of multiple returns may be considered poor style,
  38. # such a structure is often more readable than the alternatives.  In
  39. # this case, it also seems to be faster.
  40. #
  41. #  Knapsack may be tested conveniently by piping to it the output
  42. #  of randi, a trivial program, like this:
  43. #   
  44. #  iconx randi 100 10 | iconx knapsack 250
  45. #  
  46. #  You may pick a different capacity, of course; this one just
  47. #  happens to produce a result quite quickly, as you might expect.
  48. #
  49. ############################################################################
  50.  
  51. global vols,chosen,capacity
  52.  
  53. procedure main(args)
  54.     capacity := integer(args[1]) | stop("usage: knapsack capacity")
  55.     vols := []; every put(vols,0 < integer(!&input))
  56.     chosen := list(*vols,0)
  57.     # assert the requirement and write a solution
  58.     trynext(0,1) = capacity
  59.     every write(0 < !chosen)
  60.     end
  61.  
  62. #   trynext - recursively try to insert vols[n], incrementing n each
  63. #   time, while the knapsack is not full and the reference is within
  64. #   bounds
  65. procedure trynext(totvol,n)
  66.     (capacity <= totvol) & return totvol    # prune the tree for efficiency
  67.     suspend trynext(totvol + (chosen[n] := (vols[n] | 0)), n+1)
  68.     end
  69.