Programming Praxis

We look today at a famous problem known as the knapsack problem. The task is to fill a knapsack that can carry objects of a known total weight—the capacity—with objects of a given set—each object having a given weight and value—in such a way as to maximize the sum of the values of the objects. Since any individual object is subject to a binary decision to either take it or leave it, this variant of the knapsack problem is known as the 0/1 knapsack.

The usual algorithm uses dynamic programming on the recurrence expression V[i,w] = max(V[i−1,w], v_i + V[i−1,w−w_i]), where V[i,w] is the maximum value of a knapsack of capacity w using the first i objects (which must be arranged by increasing weight), v_i is the value of the ith object, and w_i is the weight of the ith object. The program builds up the V matrix, starting from V[0,w] = 0, for all weights 0 ≤ w ≤ W and all sets of objects 1 ≤ i ≤ n, where n is the number of objects available. The answer is V[n,W].

Your task is to write a function that implements the knapsack algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2