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
participants (2)
-
Bernardo B. Terrado
-
staym@accessdata.com