Navigation

The Knapsack problem

Given a set of items, where each has a value $v_i$ and a weight $w_i$ . We would like to pick certain items to maximize the total value, subject to the constraint that the total weight is at most $W$ .

We are looking for a subset

$S \lbrace 1...n \rbrace$ such that

$\sum _{i \in S} {w_{i}} <= W$ and $\sum _{i \in S}{v_{i}}$ is as large as possible.

.

Dynamic programming solution

Reference: Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 0-201-53082-1