0/1 knapsack

Hey guys,

I found this in a web site.
|---v
A knapsack that holds a total....and N indivisible objects....
My quetion is does indivisible means that the object cannot be divided as
dividing a grain of rice? Does this imply I can divide an array of
integers but not the integers? 
--------------------------------------------


If I'm going to use 0/1 knapsack algo then I'll just place a tag on each
element let us say 1 for true and 0 for false? which ever element satisfy
the condition?

What is dynamic programming approach (wavefront calculation)? Is it with
the use of pointers? or
different concept? 


Thanks.

Bernie

P.S. If you're considering writing a cipher based on them, don't.  Every
knapsack-based encryption algorithm has been broken.
-- 
Mike Stay
Cryptographer / Programmer
AccessData Corp.
mailto: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