---
tags: Dynamic Programming
title: Knapsack Problems
---

# Fractional Knapsack Problem

* Input: A sequence of weights and another of values, the capacity of knapsack.

* Output: Maximum value. (You can cut item into pieces.)

## Greedy

Sorted by $\dfrac{\text{value}}{\text{weight}}$ of each item, always choose the biggest one in that moment.

Since every unit of space in the knapsack contains the most valued item,
you cannot increase total value by changing items.

Furthermore, there's no space left in the knapsack. It's the best choice apparently.

* Time complexity: $O(N)$, where $N$ is the number of items.

---

# 0/1 Knapsack Problem

* Input: A sequence of weights and another of values, the capacity of knapsack.

* Output: Maximum value. (But cannot split the items.)

## Naive: Exhaustive Search

* Time complexity: $O(N\cdot2^N)$, where $N$ is the number of items.

Since there are $2^N$ subsets, and each validation takes $O(N)$ times.

## Dynamic Programming

$f(n, w):$ the answer when only consider the first $n$ items, and the weight is ***exactly*** $w$.

$f(n, w)=
\begin{cases}
-\infty, &\text{if } n<0 \text{ or } w<0. \\
0, &\text{if } n=0\text{ and }w\geq 0. \\
\max\{f(n-1, w), f(n-1,w-w_n)+c_n\}, &\text{otherwise}.
\end{cases}$

* Time complexity: $O(NC)$, where $N$ is the number of items, and $C$ is the capacity
(pseudo polynomial time)

## Implementation

### Top-down:

vector<int> c, w;
vector<vector<int>> dp;

int knapsack(int n, int w) {
    if (w < 0) return -0x3fffffff;
    if (n == 0) return 0;

    if (dp[n][w]) return dp[n][w];
    return dp[n][w] = max(
        knapsack(n - 1, w), knapsack(n - 1, w - w[n]) + c[n]
        );
}

### Bottom-up:

vector<int> c, w;

int knapsack(int N, int W) {
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));

    for (int i = 0; i < N; ++i) { 
        for(int j = 0; j <= W; ++j) {
            if (j - w[i] < 0) 
                dp[i + 1][j] = dp[i][j];
            else
                dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + c[i]);
        }
    }
    return dp[N][W];
}

### Bottom-up (with space optimization):

    vector<int> c, w;

    int knapsack(int N, int W) {
        vector<int> dp(W + 1, 0);

        for (int i = 0; i < N; ++i) { 
            for (int j = W; j - w[i] >= 0; --j) {
                dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
            }
        }
        return dp[W];
    }

---

# Unbounded (Infinite) Knapsack Problem

* Input: A sequence of weights and another of values, the capacity of knapsack.

* Output: Maximum value. (items can be taken infinite times.)

## Dynamic Programming

$f(n, w):$ the answer when only consider the first $n$ items, and the weight is ***exactly*** $w$.

$f(n, w)=
\begin{cases}
-\infty, &&\text{if } n<0 \text{ or } w<0. \\
0, &&\text{if } n=0\text{ and }w\geq 0. \\
\max\{&f(n-1, w), \\ &f(n-1,w-w_n)+c_n, \\ &f(n-1, w-2w_n)+2c_n, \\ &\vdots \\ &~~~~~~~\}, &\text{otherwise}.
\end{cases}$

## A Better Way of Dynamic Programming

$f(n, w):$ the answer when only consider the first $n$ items, and the weight is ***exactly*** $w$.

$f(n, w)=
\begin{cases}
-\infty, &\text{if } n<0 \text{ or } w<0. \\
0, &\text{if } n=0\text{ and }w\geq 0. \\
\max\{f(n-1, w), f(n,w-w_n)+c_n\}, &\text{otherwise}.
\end{cases}$

* Time complexity: $O(NC)$, where $N$ is the number of items, and $C$ is the capacity

## Implementation

vector<int> c, w;

int knapsack(int N, int W) {
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < N; ++i) {
        for (int j = w[i]; j <= W; ++j) { 
        // After space optimization,
        // the loop direction is the only difference with 0/1 knapsack problem
            dp[j] = max(dp[j], dp[j - w[i]] + c[j]);
        }
    }
    return dp[W];
}

---

# Bounded (Finite) Knapsack Problem

* Input: A sequence of weights and another of values, the capacity of knapsack.

* Output: Maximum value. (items can be taken certain number times.)

## Dynamic Programming

$f(n, w):$ the answer when only consider the first $n$ items, and the weight is ***exactly*** $w$.

$f(n, w)=
\begin{cases}
-\infty, &&\text{if } n<0 \text{ or } w<0. \\
0, &&\text{if } n=0\text{ and }w\geq 0. \\
\max\{&f(n-1, w), \\ &f(n-1,w-w_n)+c_n, \\ &f(n-1, w-2w_n)+2c_n, \\ &\vdots \\ &f(n-1, w-k_nw_n)+k_nc_n\}, &\text{otherwise}.
\end{cases}$

## A Better Way of Dynamic Programming

We can split $k_n$ items into groups of $1, 2, 4, 8, \dots, 2^h, k_n-2^h$, $\lceil\log k_n\rceil$ groups in total.

And use these groups to simplify bounded knapsack into 0/1 knapsack.

* Time complexity: $O(NC\log K)$,
where $N$ is the number of items, $C$ is the capacity, $K$ is the maximum of $k_i$

## Implementation

vector<int> c, w, k;

void knapsack(int N, int W) {
    vector<int> dp(W + 1);
    
    for (int i = 0; i < N; ++i) {
        int num = min(k[i], W / w[i]);
        for (int n = 1; n > 0; n *= 2) {
            if (n > num) n = num;
            num -= n;
            for (int j = W; j >= n * w[i]; --j) {
                dp[j] = max(dp[j], dp[j - n * w[i]] + n * c[i]);
            }
        }
    }
    return dp[W];
}

## More optimization

* http://www.cnblogs.com/GXZC/archive/2013/01/08/2851153.html

* http://morris821028.github.io/2016/12/18/jg-20008/