Knapsack Problem

Given n items:
weights:    w1    w2  …  wn
values:       v1     v2  …  vn
a knapsack of capacity W

Find most valuable subset of the items that fit into the knapsack

Example: Knapsack capacity W=16

Item  weight  value
1        2          $20
2        5          $30
3       10         $50
4        5          $10