3/19/2018

1

6.4 Knapsack Problem |

27

Knapsack Problem

Knapsack problem.

■ Given n items and a “knapsack“ such that

– item i weighs wi > 0 and has value vi > 0, and

– the knapsack has the capacity of total weight W.

■ Goal: fill the knapsack so as to maximize the total value, i.e., find a

subset S of the set of n items such that Σi∈Svi is maximized subject

to Σi∈Swi ≤ W.

Ex: Optimal solution for this one?

The optimal solution is items 3, 4

which has the total value 40. 1

Value

18

22

28

1

Weight

5 6

6 2

7

Item

1 2 3 4 5

W = 11

3/19/2018

2

Side Note: 0-1 Knapsack Problem

28

Greedy: repeatedly add an item with the maximum ratio vi/wi, subject

to the capacity limit of W.

Q. Is this greedy optimal?

A. No!

This greedy finds items 5, 2, 1 which achieves only value 35.

29

Knapsack Problem: Greedy ?

1

Value

18

22

28

1

Weight

5 6

6 2

7

Item

1 2 3 4 5

W = 11

Value/Weight

1

3.6

3.66…

3 4

3/19/2018

3

30

Dynamic Programming: As We Did Before

Notation. OPT(i) = max total value of the items in an optimal subset of

items 1, 2, .., i .

To compute OPT(i):

■ Case 1: item i is not in the optimal solution.

– OPT(i) is computed from the remaining items 1, 2, …, i-1

– So, OPT(i) = OPT(i-1)

■ Case 2: item i is in the optimal solution.

– OPT(i) is the sum of vi and the total value of an optimal solution

from the remaining items 1, 2, …, i-1

– So, OPT(i) = vi + OPT(i-1)

■ So, OPT(i) = max OPT(i-1), vi + OPT(i-1) = vi + OPT(i-1) Not right!

■ What’s wrong? Accepting an item i changes the available capacity of

the knapsack, which is one of the variables defining the problem. So,

we need to redefine the subproblems to involve the available capacity.

31

Dynamic Programming: Now Differently (and Correctly)

Notation. OPT(i, w) = max total value of items in an optimal subset of

items 1, 2, .., i subject to the total weight limit w.

■ Case 1: item i is not in the optimal solution.

– OPT(i, w) is computed from the remaining items 1, 2, …, i-1

subject to the total weight limit w.

■ Case 2: item i is in the optimal solution (possible only if wi ≤ w).

– new weight limit = w – wi

– OPT(i, w) is the sum of vi and the total value of an optimal solution

from the remaining items 1, 2, …, i-1 subject to the total weight

limit w – wi.

OPT(i, w) =

0 if i = 0

OPT(i -1, w) if wi > w

max OPT(i -1, w), vi + OPT(i -1, w – wi ) otherwise

Optimal substructure:

3/19/2018

4

Knapsack. Fill up an array M[0..n][0..W]. (Assume integer weights.)

■ (We have a two-variable OPT(i, w), so we need a two-dimensional

array.)

32

Input: W, w1,…,wn, v1,…,vn

Global array: M[0..n][0..W]

for w = 0 to W

M[0, w] = 0

for i = 1 to n

for w = 0 to W

if (wi > w)

M[i,w] = M[i-1,w]

else

M[i,w] = maxM[i-1,w], vi + M[i-1,w-wi]

return M[n, W]

Knapsack Algorithm: Bottom-Up

OPT(i, w) =

0 OPT(i -1, w) |
if i = 0 if wi > w |

max OPT(i -1, w), vi + OPT(i -1, w – wi ) otherwise

33

Knapsack Algorithm: Tracing

i

φ

1, 2

1, 2, 3

1, 2, 3, 4

1

1, 2, 3, 4, 5

0 0 0 0 0 0 0

1 0 1 1 1 1 1

2 0 1 6 6 6 6

3 0 1 7 7 7 7

4 0 1 7 7 7 7

5 0 7

18

18

1

18

6 0 7

19

22

1

22

7 0 7

24

24

1

28

8 0 7

25

28

1

29

9 0 7

25

29

1

34

10

0 7

25

29

1

35

11

0 7

25

40

1

40

w

1

Value

18

22

28

1

Weight

5 6

6 2

7

Item

1 2 3 4 5

W = 11

value = 22 + 18 = 40 (for 4, 3 )

for w = 0 to W

M[0, w] = 0

for i = 1 to n

for w = 0 to W

if (wi > w)

M[i, w] = M[i-1, w]

else

M[i, w] = maxM[i-1, w],

vi + M[i-1, w-wi]

3/19/2018

5

34

Knapsack Problem: Running Time

Running time. Θ(n W).

■ Polynomial in n and W, but see the note below.

Note. This is not a polynomial algorithm.

– There are two inputs: items (i.e., their values and weights) and

knapsack capacity.

– n, number of items, is not an input but its cardinality.

So, the runtime has nothing to do with the numeric values of

the values of items.

– W, capacity, is the numeric value of an input, i.e., limit on max total

weight.

So, if W is very large, the runtime is very long.

– Computationally, we say the running time Θ(n W) = Θ(n 2b), where b

is the length of the binary representation of W. So, exponential!

This kind of running time is called pseudo-polynomial. (More

on this later when we are studying NP.)

Side Note: Pseudo-polynomial Runtime

Def. Pseudo-polynomial: polynomial in the magnitude of the input

values but not in the number of bits needed to represent the values.

“A numeric algorithm runs in pseudo-polynomial time if its running

time is polynomial in the numeric value of the input (which is

exponential in the length of the input — its number of digits). “ –

Wikipedia

Compare: “really”-polynomial runtime – examples:

– Dijkstra’s shortest-path finding algorithm: O(m logn), where m is

the number of edges and n is the number of vertices, either of

which has nothing to do with the weights of the edges.

– Weighted interval scheduling algorithm: O(n), where n is the

number of jobs, which has nothing to do with the weights of the

jobs.

35

3/19/2018

6

Knapsack: Finding a Solution

To find an optimal subset of items in addition to the optimal total value

of them.

Idea (Bookkeeping). Record the “winning case” (item i included or not

subject to weight limit w) in the array entry M[i,w] at each step of

the iteration, and then backtrack from M[n,W] to collect items that

are included.

Idea (Post-processing). Trace the array M[0..n][0..W] backward

recursively starting with the last element M[n][W].

Exercise!

36

37

Side Note: Knapsack Problem — Greedy (Again)

Q. What if we allow part of an item to be included? What difference

would it make?

■ (Note: In this case we call it the fractional knapsack problem; in

contrast, we call the original one the 0-1 knapsack problem.)

Q. Does greedy work?

■ Greedy choice strategy: include the item with the largest

value/weight ratio first.

A. Yes, greedy works! The greedy finds items item 5, 2/3 of item 4 ,

achieving 42.666… which is the optimal value.

Running-time:

1

Value

18

22

28

1

Weight

5 6

6 2

7

Item

1 2 3 4 5

W = 11

Value/Weight

1

3.6

3.66…

3 4

O(n logn) for sorting

the items by the ratio

value/weight.

The post Knapsack Problem appeared first on My Assignment Online.