concept 0 - 1 knapsack problem in category algorithms

This is an excerpt from Manning's book Algorithms and Data Structures in Action MEAP V14. Login to get full access to this book.

There is, however, also good news: there exist a pseud-polynomial[8] solution, a solution using dynamic programming[9] that takes time proportional to the max capacity of the knapsack, and luckily the capacity of the crate is limited: it takes a number of steps equal to the number of possible values for the capacity filled multiplied by the number of items, so assuming the smallest unit is 1kg, it only takes 1000 * 62 steps. Wow, that’s much better than 262! And, in fact, once you rewrite the algorithm, it finds the best solution in a matter of seconds.

But perhaps the best way to understand genetic algorithms is by seeing them in action; to that extent, and to keep things concrete, while we describe all the building blocks of this meta-algorithm, we’ll develop an example along the way, to help readers visualize how each component works: do you remember the 0-1 knapsack problem? We are going all the way back to chapter 1, when we introduced this problem to model our “packing to Mars” situation – back then, we mentioned there is a pseudo-polynomial dynamic algorithm that can provide the absolute best solution, but it can be too slow when the capacity of the knapsack is large. Branch-and-bound approximated algorithms exist that can compute near-optimal solutions (with some guarantees on the upper bound, and in reasonable time), although the efficient ones are usually quite complex[8].

Figure 18.7 Tournament selection, applied to our instance of the 0-1 knapsack problem.