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 , =0 or , subject to the constraint ≤c.
x
i
v
i
w
i
i=1,…,5
v
i
w
i
5
∑
i=1
ϵ
i
v
i
ϵ
i
1
5
∑
i=1
ϵ
i
w
i