[105642] in Cypherpunks
Re: 0/1 knapsack
daemon@ATHENA.MIT.EDU (staym@accessdata.com)
Tue Nov 17 13:35:46 1998
From: staym@accessdata.com
Date: Tue, 17 Nov 1998 11:00:52 -0700
To: "Bernardo B. Terrado" <bbt@mudspring.uplb.edu.ph>
CC: cypherpunks@toad.com, coderpunks@toad.com
Reply-To: staym@accessdata.com
A knapsack is a container that can only hold so much of something. You
have a collection of objects with a weight and/or volume and a value.
You want to maximize the value. Fractional knapsack problems concern
things like flour and sugar, that you can measure out a fractional unit
of. In 0/1 knapsack problems, you have a collection of objects: either
you put in the TV or you don't; no half-TV's.
Quoting from _Introduction to Algorithms_ (Cormen, Leiserson, & Rivest),
'Dynamic programming, like the divide-and-conquer method, solves
problems by combining the solutions to subproblems. ("Programming" in
this context refers to a tabular method, not to writing computer code.)
... Divide-and-conquer algorithms partition the problem into independant
subproblems, solve the problems recursively, and then combine their
solutions to solve the original problem. In contrast, dynamic
programming is applicable when the subproblems are not independent..."
--
Mike Stay
Cryptographer / Programmer
AccessData Corp.
mailto:staym@accessdata.com
