Navigation

Amazon.com Widgets

The Knapsack problem

Given a set of items, where each has a value tex:v_i and a weight tex: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 tex:W .

We are looking for a subset

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

$tex:\sum _{i \in S} {w_{i}} <= W$ and $tex:\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