The unbounded knapsack

Lesson · 9 min read · Dynamic programming · Unbounded knapsack

Every item can be taken any number of times. One array, filled upwards, and the recurrence reads its own row.

Reuse changes one index

With unlimited copies, taking item i does not use it up: after taking it we may take it again. In the two-dimensional recurrence, "take" now stays in row i:

best(i, c) = max( best(i − 1, c), value[i] + best(i, c − weight[i]) )

Because the order of items no longer matters for an optimum, the item index can be dropped altogether: best(c) = max over items of value[i] + best(c − weight[i]), with best(0) = 0. Rod cutting (sell pieces of a rod at given prices) and fewest coins are the same recurrence with min instead of max.

Items 2 kg worth 3, 3 kg worth 5, 5 kg worth 9, any number of each, capacities 0 to 9.

Step 1 / 10

best
00·1·2·3·4·5·6·7·8·9
Base case: best[0] = 0.
Step 2 / 10

best
0001·2·3·4·5·6·7·8·9
Capacity 1: nothing fits; the best is 0.
Step 3 / 10

best
000132·3·4·5·6·7·8·9
Capacity 2: 3 + best[0]; the best is 3.
Step 4 / 10

best
00013253·4·5·6·7·8·9
Capacity 3: 3 + best[1], 5 + best[0]; the best is 5.
Step 5 / 10

best
0001325364·5·6·7·8·9
Capacity 4: 3 + best[2], 5 + best[1]; the best is 6.
Step 6 / 10

best
000132536495·6·7·8·9
Capacity 5: 3 + best[3], 5 + best[2], 9 + best[0]; the best is 9.
Step 7 / 10

best
000132536495106·7·8·9
Capacity 6: 3 + best[4], 5 + best[3], 9 + best[1]; the best is 10.
Step 8 / 10

best
000132536495106127·8·9
Capacity 7: 3 + best[5], 5 + best[4], 9 + best[2]; the best is 12.
Step 9 / 10

best
000132536495106127148·9
Capacity 8: 3 + best[6], 5 + best[5], 9 + best[3]; the best is 14.
Step 10 / 10

best
000132536495106127148159
Capacity 9: 3 + best[7], 5 + best[6], 9 + best[4]; the best is 15. best[9] = 15: for example 5 kg + 2 kg + 2 kg (9 + 3 + 3).

The loop direction is the whole difference

def unbounded_knapsack(weights, values, cap):
    best = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(w, cap + 1):            # upwards: best[c - w] may already use this item
            best[c] = max(best[c], v + best[c - w])
    return best[cap]

int unbounded_knapsack(const std::vector<int>& weights, const std::vector<int>& values, int cap) {
    std::vector<int> best(cap + 1, 0);
    for (size_t k = 0; k < weights.size(); ++k)
        for (int c = weights[k]; c <= cap; ++c)        // upwards: best[c - w] may already use this item
            best[c] = std::max(best[c], values[k] + best[c - weights[k]]);
    return best[cap];
}

static int unboundedKnapsack(int[] weights, int[] values, int cap) {
    int[] best = new int[cap + 1];
    for (int k = 0; k < weights.length; k++)
        for (int c = weights[k]; c <= cap; c++)       // upwards: best[c - w] may already use this item
            best[c] = Math.max(best[c], values[k] + best[c - weights[k]]);
    return best[cap];
}

function unboundedKnapsack(weights, values, cap) {
    const best = new Array(cap + 1).fill(0);
    weights.forEach((w, k) => {
        for (let c = w; c <= cap; c++)                // upwards: best[c - w] may already use this item
            best[c] = Math.max(best[c], values[k] + best[c - w]);
    });
    return best[cap];
}

fn unbounded_knapsack(weights: &[usize], values: &[i64], cap: usize) -> i64 {
    let mut best = vec![0i64; cap + 1];
    for (&w, &v) in weights.iter().zip(values) {
        for c in w..=cap {                            // upwards: best[c - w] may already use this item
            best[c] = best[c].max(v + best[c - w]);
        }
    }
    best[cap]
}

unboundedKnapsack :: [Int] -> [Int] -> Int -> Int
unboundedKnapsack weights values cap = last (foldl add (replicate (cap + 1) 0) (zip weights values))
  where
    -- the new row reads itself at c - w, so the same item can be taken again
    add best (w, v) = elems row
      where
        old = listArray (0, cap) best :: Array Int Int
        row = listArray (0, cap)
          [ if c >= w then max (old ! c) (v + row ! (c - w)) else old ! c | c <- [0 .. cap] ] :: Array Int Int

Downwards: each item at most once (0/1). Upwards: each item any number of times (unbounded). Being able to say why is a common interview question.

Implementation

In six languages:

def knapsack_unbounded(weights, values, capacity):
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(w, capacity + 1):       # upwards: the item may be reused
            best[c] = max(best[c], v + best[c - w])
    return best[capacity]

#include <algorithm>
#include <vector>

long long solve(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
    std::vector<long long> best(capacity + 1, 0);
    for (size_t i = 0; i < weights.size(); ++i)
        for (int c = weights[i]; c <= capacity; ++c)   // upwards: reuse allowed
            best[c] = std::max(best[c], values[i] + best[c - weights[i]]);
    return best[capacity];
}

class Solution {
    public long knapsackUnbounded(int[] weights, int[] values, int capacity) {
        long[] best = new long[capacity + 1];
        for (int i = 0; i < weights.length; i++)
            for (int c = weights[i]; c <= capacity; c++)   // upwards: reuse allowed
                best[c] = Math.max(best[c], values[i] + best[c - weights[i]]);
        return best[capacity];
    }
}

function knapsackUnbounded(weights, values, capacity) {
  const best = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++)
    for (let c = weights[i]; c <= capacity; c++)       // upwards: reuse allowed
      best[c] = Math.max(best[c], values[i] + best[c - weights[i]]);
  return best[capacity];
}

fn solve(weights: &[i64], values: &[i64], capacity: i64) -> i64 {
    let cap = capacity as usize;
    let mut best = vec![0i64; cap + 1];
    for (&w, &v) in weights.iter().zip(values) {
        for c in (w as usize)..=cap {                   // upwards: reuse allowed
            best[c] = best[c].max(v + best[c - w as usize]);
        }
    }
    best[cap]
}

import Data.Array

solve :: [Int] -> [Int] -> Int -> Int
solve weights values capacity = best ! capacity
  where
    items = zip weights values
    -- best ! c depends only on smaller capacities, so a lazy array computes it in the right order
    best = listArray (0, capacity) [maximum (0 : [v + best ! (c - w) | (w, v) <- items, w <= c]) | c <- [0 .. capacity]] :: Array Int Int

The same code is the reference solution to The unbounded knapsack, where it is compiled and run against the tests in all six languages.

TimeO(n · capacity)

SpaceO(capacity)