0-1 Knapsack Problem

x

5

x

5

=

{25,25}

x

4

x

4

=

{25,25}

x

3

x

3

=

{25,25}

x

2

x

2

=

{25,25}

x

1

x

1

=

{25,25}

weight constraint

c

125.

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

x

i

=(

v

i

,

w

i

)

,

i=1,…,5

, where the

v

i

are values and the

w

i

are weights. The Demonstration maximizes

5

∑

i=1

ϵ

i

v

i

,

ϵ

i

=0

or

1

, subject to the constraint

5

∑

i=1

ϵ

i

w

i

≤c

.