Knapsack Problem

SOLUTION AT Australian Expert Writers

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.

Order from Australian Expert Writers
Best Australian Academic Writers

QUALITY: 100% ORIGINAL PAPERNO PLAGIARISM – CUSTOM PAPER