Solving Knapsack Problem with Dynamic Programming

Posted on | Post modified | In , , ,

Problem

Goal: Pack knapsack so as to maximize total value.

  • There are n items: item i provides value vi > 0 and weights wi > 0
  • Knapsack has weight capacity of W

Assumption: All input values are integral

How to develop a dynamic programming algorithm

Define

OPT(i, w) = max-profit subset of items 1, …, i with weight limit w.

Goal

get OPT(n, W).

There are two cases

Case 1: OPT(i, w) does not select item i.

  • IOT(i, w) selects best of {1, 2, …, i - 1} using weight limit w

Case 2: OPT(i, w) selects item i.

  • Collect value vi
  • New weight limit = w - wi
  • OPT(i, w) selects best of {1, 2, …, i - 1} using this new weight limit

Bellman equation

OPT(i, w) = 0 , if i = 0

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# W = 6, 
# v1 = 3, w1 = 4
# v2 = 2, w2 = 3
# v3 = 4, w3 = 2
# v4 = 4, w4 = 3

def knapsack(W, n, values, weights):
    table = [[0 for _ in range(W + 1)] for _ in range(n + 1)]

    for item in range(1, n + 1):
        for w in range(W + 1):
            if weights[item - 1] > w:
                table[item][w] = table[item - 1][w]
            else:
                table[item][w] = max(table[item - 1][w], \
                                     table[item - 1][w - weights[item - 1]] + \
                                     values[item - 1])
    return table[n][W]


values = [3, 2, 4, 4]
weights = [4, 3, 2, 3]
W = 6
n = len(values)

print(knapsack(W, n, values, weights))

After computing optimal values, we can trace back to find which item should be selected:

OPT(i, w) takes item i if and only if $table[i][w] > table[i - 1][w]$

Reference

https://www.coursera.org/lecture/algorithms-greedy/the-knapsack-problem-LIgLJ

http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/06DynamicProgrammingI-2x2.pdf