# 0-1 Knapsack Problem

0-1 Knapsack Problem

The knapsack problem is to choose which objects (on the left) maximize the total value of the knapsack contents (on the right) subject to a total weight constraint. The 0-1 refers to a restriction: zero or one of each object.

The objects are , , where the are values and the are weights. The Demonstration maximizes , or , subject to the constraint .

x=(v,w)

i

i

i

i=1,…,5

v

i

w

i

∑ϵv

5

i=1

i

i

ϵ=0

i

1

∑ϵw≤c

5

i=1

i

i