Knapsack DP

Prerequisite knowledge: Introduction to Dynamic Programming．

Introduction

Before explaining what “knapsack DP” is, consider the following example:

In the example above, each object has only two possible states (selected or not selected), corresponding to $0$ and $1$ in binary. Such problems are called “0-1 knapsack problems”．

0-1 Knapsack

Explanation

The known conditions in the example are the weight $w_{i}$ and value $v_{i}$ of item $i$, as well as the total capacity $W$ of the knapsack．

Let the DP state $f_{i,j}$ be the maximum total value attainable by a knapsack of capacity $j$ when only the first $i$ items may be placed in it．

Consider the transition. Suppose all states for the first $i-1$ items have already been processed. For item $i$, if it is not put into the knapsack, the remaining capacity and total value remain unchanged, so the maximum value in this case is $f_{i-1,j}$. If it is put into the knapsack, the remaining capacity decreases by $w_{i}$ and the total value increases by $v_{i}$, so the maximum value is $f_{i-1,j-w_{i}}+v_{i}$．

Thus the state transition is

Recording the states directly in a two-dimensional array causes MLE. A rolling array can be used for optimization．

Only $f_i$ is affected by $f_{i-1}$, so the first dimension can be removed. Let $f_{i}$ directly denote the maximum value for capacity $i$ after processing the current item. We obtain

Be sure to remember and understand this transition, because the transitions for most knapsack problems are derived from it．

Implementation

One thing to note is that it is easy to write the following incorrect core code:

C++

for (int i = 1; i <= n; i++)
  for (int l = 0; l <= W - w[i]; l++)
    f[l + w[i]] = max(f[l] + v[i], f[l + w[i]]);
// Simplified from f[i][l + w[i]] = max(max(f[i - 1][l + w[i]], f[i - 1][l] + v[i]),
// f[i][l + w[i]])

Python

for i in range(1, n + 1):
    for l in range(0, W - w[i] + 1):
        f[l + w[i]] = max(f[l] + v[i], f[l + w[i]])
# Simplified from f[i][l + w[i]] = max(max(f[i - 1][l + w[i]], f[i - 1][l] + v[i]),
# f[i][l + w[i]])

What is wrong with this code? The enumeration order is wrong．

Observe carefully that for the currently processed item $i$ and current state $f_{i,j}$, when $j\geqslant w_{i}$, $f_{i,j}$ is affected by $f_{i,j-w_{i}}$. This is equivalent to putting item $i$ into the knapsack multiple times, which does not match the problem statement. (In fact, this is the solution to the unbounded knapsack problem．)

To avoid this, we can change the enumeration order to go from $W$ down to $w_{i}$. Then the above error does not occur, because $f_{i,j}$ is always updated before $f_{i,j-w_{i}}$．

Thus the actual core code is

C++

for (int i = 1; i <= n; i++)
  for (int l = W; l >= w[i]; l--) f[l] = max(f[l], f[l - w[i]] + v[i]);

Python

for i in range(1, n + 1):
    for l in range(W, w[i] - 1, -1):
        f[l] = max(f[l], f[l - w[i]] + v[i])

#include <iostream>
using namespace std;
constexpr int MAXN = 13010;
int n, W, w[MAXN], v[MAXN], f[MAXN];

int main() {
  cin >> n >> W;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];  // Read the data
  for (int i = 1; i <= n; i++)
    for (int l = W; l >= w[i]; l--)
      if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];  // State transition
  cout << f[W];
  return 0;
}

Unbounded Knapsack

Explanation

The unbounded knapsack model is similar to 0-1 knapsack. The only difference is that an item may be selected infinitely many times rather than only once．

We can borrow the idea of 0-1 knapsack and define the state as follows: let $f_{i,j}$ be the maximum value attainable by a knapsack of capacity $j$ when only the first $i$ items may be selected．

Note that although this definition is similar to that of 0-1 knapsack, its state transition is different．

Process

A naive approach is to enumerate how many copies of item $i$ are selected for each transition. This has time complexity $O(n^3)$．

The transition is

Consider a simple optimization. For $f_{i,j}$, it is enough to transition through $f_{i,j-w_i}$. Thus the transition becomes

The reason is that when making this transition, $f_{i,j-w_i}$ has already been updated from $f_{i,j-2\times w_i}$, so $f_{i,j-w_i}$ is the optimal result after fully considering how many copies of item $i$ are selected. In other words, we reuse the previous enumeration through the optimal-substructure property and reduce the enumeration complexity．

As with 0-1 knapsack, we can remove the first dimension to optimize space complexity. Once the 0-1 knapsack optimization is understood, it is not difficult to see that the compressed loop runs forward (that is, it uses the incorrect optimization mentioned above)．

#include <iostream>
using namespace std;
constexpr int MAXN = 1e4 + 5;
constexpr int MAXW = 1e7 + 5;
int n, W, w[MAXN], v[MAXN];
long long f[MAXW];

int main() {
  cin >> W >> n;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
  for (int i = 1; i <= n; i++)
    for (int l = w[i]; l <= W; l++)
      if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];  // Core transition
  cout << f[W];
  return 0;
}

Bounded Knapsack

Bounded knapsack is another variant of 0-1 knapsack. The difference is that there are $k_i$ copies of each type of item rather than one．

A very naive idea is to convert “select each type of item $k_i$ times” into “there are $k_i$ identical items, each selected once.” This converts it into a 0-1 knapsack model, which can be solved using the method above. The transition is

The time complexity is $O(W\sum_{i=1}^nk_i)$．

for (int i = 1; i <= n; i++) {
  for (int weight = W; weight >= w[i]; weight--) {
    // Iterate one more layer over the item count
    for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++) {
      dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]);
    }
  }
}

Binary Grouping Optimization

Consider an optimization. We still solve bounded knapsack by converting it into a 0-1 knapsack model．

Explanation

The $O(nW)$ part of the complexity clearly cannot be optimized further, so we can only work on the $O(\sum k_i)$ part. For convenience, let $A_{i,j}$ denote the $j$th item obtained by splitting type $i$．

In the naive approach, for every $\forall j\le k_i$, $A_{i,j}$ represents the same item. The main reason for the low efficiency is the large amount of repeated work. For example, we consider both “select $A_{i,1},A_{i,2}$ together” and “select $A_{i,2},A_{i,3}$ together,” which are completely equivalent. This repetition occurs many times. Thus, improving the splitting method is the key to solving the problem．

Process

We can make the splitting method more elegant through “binary grouping”．

Specifically, let $A_{i,j}\left(j\in\left[0,\lfloor \log_2(k_i+1)\rfloor-1\right]\right)$ represent a large item formed by “bundling” $2^{j}$ individual items. If $k_i+1$ is not an integer power of $2$, add one final large item formed by “bundling” $k_i-2^{\lfloor \log_2(k_i+1)\rfloor-1}$ individual items to make up the remainder．

For example:

• $6=1+2+3$
• $8=1+2+4+1$
• $18=1+2+4+8+3$
• $31=1+2+4+8+16$

Clearly, this splitting method can represent every equivalent choice of at most $\le k_i$ items. After splitting each type of item in this way, apply the 0-1 knapsack method．

The time complexity is $O(W\sum_{i=1}^n\log_2k_i)$．

Implementation

index = 0;
for (int i = 1; i <= m; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k;
  while (k > c) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}

index = 0
for i in range(1, m + 1):
    c = 1
    p, h, k = map(int, input().split())
    while k > c:
        k -= c
        index += 1
        list[index].w = c * p
        list[index].v = c * h
        c *= 2
    index += 1
    list[index].w = p * k
    list[index].v = h * k

Monotone Queue Optimization

See Monotone queue/monotone stack optimization．

Exercise: 「Luogu P1776」Treasure Selection_NOI Guide 2010 Advanced (02)

Mixed Knapsack

Mixed knapsack combines the three knapsack problems above: some items can be selected only once, some infinitely many times, and some at most $k$ times．

Such problems may look intimidating, but once the central ideas of the preceding knapsack types are understood and combined, they become manageable. The pseudocode is as follows:

for (each item type) {
  if (the item is 0-1 knapsack)
    apply the 0-1 knapsack transition;
  else if (the item is complete knapsack)
    apply the complete-knapsack transition;
  else if (the item is bounded knapsack)
    apply the bounded-knapsack transition;
}

Example Problem

for (int i = 1; i <= n; i++) {
  if (cnt[i] == 0) {  // If the count is unlimited, use the core unbounded-knapsack code
    for (int weight = w[i]; weight <= W; weight++) {
      dp[weight] = max(dp[weight], dp[weight - w[i]] + v[i]);
    }
  } else {  // For limited items, use the core bounded-knapsack code; it also handles 0-1 knapsack
    for (int weight = W; weight >= w[i]; weight--) {
      for (int k = 1; k * w[i] <= weight && k <= cnt[i]; k++) {
        dp[weight] = max(dp[weight], dp[weight - k * w[i]] + k * v[i]);
      }
    }
  }
}

Exercise: HDU 5410 CRB and His Birthday

Knapsack with Two-Dimensional Costs

This is clearly a 0-1 knapsack problem, but selecting an item consumes two resources (money and time). We only need to add one dimension to the state to store the second resource．

At this point, adding another dimension for the item number is unsuitable because it can easily cause MLE．

Implementation

C++

for (int k = 1; k <= n; k++)
  for (int i = m; i >= mi; i--)    // Enumerate the budget layer
    for (int j = t; j >= ti; j--)  // Enumerate the time layer
      dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1);

Python

for k in range(1, n + 1):
    for i in range(m, mi - 1, -1):  # Enumerate the budget layer
        for j in range(t, ti - 1, -1):  # Enumerate the time layer
            dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1)

Group Knapsack

How should this problem be approached? It changes “select one item from all items” into “select one item from the current group,” so we can perform one 0-1 knapsack for each group．

As for storage, let $t_{k,i}$ denote the item number of the $i$th item in group $k$, and let $\mathit{cnt}_k$ denote the number of items in group $k$．

Implementation

C++

for (int k = 1; k <= ts; k++)          // Loop over each group
  for (int i = m; i >= 0; i--)         // Loop over knapsack capacities
    for (int j = 1; j <= cnt[k]; j++)  // Loop over every item in the group
      if (i >= w[t[k][j]])             // The knapsack has enough capacity
        dp[i] = max(dp[i],
                    dp[i - w[t[k][j]]] + c[t[k][j]]);  // Transition as in 0-1 knapsack

Python

for k in range(1, ts + 1):  # Loop over each group
    for i in range(m, -1, -1):  # Loop over knapsack capacities
        for j in range(1, cnt[k] + 1):  # Loop over every item in the group
            if i >= w[t[k][j]]:  # The knapsack has enough capacity
                dp[i] = max(
                    dp[i], dp[i - w[t[k][j]]] + c[t[k][j]]
                )  # Transition as in 0-1 knapsack

Be careful: the loop order must not be wrong, otherwise correctness cannot be guaranteed．

Knapsack with Dependencies

Consider the cases. For a main item and several attachments, the possibilities are to buy only the main item or the main item together with some attachments. Since only one of these possibilities can be selected, this can be viewed as group knapsack．

If the items form a collection of multiway trees, first calculate the collection for the child nodes, and finally the collection for the parent node．

Knapsack of Generalized Items

In this knapsack variant, the cost and value are not fixed; its value depends on the cost allocated to it. In a knapsack of capacity $V$, when the cost allocated to it is $v_i$, the value obtained is $h\left(v_i\right)$. Thus, replace the fixed value with a function reference．

Miscellaneous

Small Optimizations

By the greedy principle, when costs are equal, keep only the item with the highest value; when values are fixed, keep only the item with the lowest cost; if there are two items $i,j$ such that item $i$ has a higher value than item $j$ and item $i$ has a lower cost than item $j$, keep only $i$．

Variants of Knapsack Problems

Outputting a Solution

Outputting a solution means recording how a certain state in the knapsack was derived. Let $g_{i,v}$ indicate whether item $i$ is selected when it occupies space $v$. During the transition, record which strategy was used (selected or not selected). The pseudocode for output is:

int v = V;  // Record the current storage space

// Since the last item stores the final state, loop from the last item
for (items from last to first) {
  if (g[i][v]) {
    select item i;
    v -= weight[i];
  } else {
    do not select item i;
  }
}

Counting the Number of Solutions

Given a knapsack capacity, item costs, and other relations, count the total number of ways to fill the knapsack to a certain capacity．

This problem is solved by replacing maximization with summation．

For example, the transition for 0-1 knapsack becomes

Initial condition: $\mathit{dp}_0=1$．

This is because when the capacity is $0$, there is still one solution: selecting nothing．

Counting Optimal Solutions

To count optimal solutions, slightly modify the definition of the $\mathit{dp}$ array in 0-1 knapsack. Let the DP state $f_{i,j}$ be the maximum total value attainable when the knapsack contains exactly volume $j$ and only the first $i$ items may be used．

After this modification, each DP state can be associated with a $g_{i,j}$ representing the number of solutions．

$f_{i,j}$ is the maximum value when considering only the first $i$ items and the knapsack volume is exactly $j$．

$g_{i,j}$ is the number of solutions when considering only the first $i$ items and the knapsack volume is exactly $j$．

The transition is as follows:

If $f_{i,j} = f_{i-1,j}$ and $f_{i,j} \neq f_{i-1,j-v}+w$, not selecting the item is better, so the number of solutions comes from $g_{i-1,j}$．

If $f_{i,j} \neq f_{i-1,j}$ and $f_{i,j} = f_{i-1,j-v}+w$, selecting the item is better, so the number of solutions comes from $g_{i-1,j-v}$．

If $f_{i,j} = f_{i-1,j}$ and $f_{i,j} = f_{i-1,j-v}+w$, both selecting and not selecting achieve an optimal solution, so the number of solutions comes from $g_{i-1,j}$ and $g_{i-1,j-v}$．

Initial conditions:

memset(f, 0xcf, sizeof(f));
// Since this is a maximization, initialize to negative infinity to avoid transitions from unfilled states
// For minimization, initialize to positive infinity 0x3f
f[0] = 0;
g[0] = 1;  // Selecting nothing is one solution

Because the maximum knapsack volume may not be filled, the optimal solution is not necessarily $f_{m}$．

Finally, find the value of the optimal solution and add up all solution counts in the $g_{j}$ array that attain this value．

for (int i = 0; i < N; i++) {
  for (int j = V; j >= v[i]; j--) {
    int tmp = std::max(dp[j], dp[j - v[i]] + w[i]);
    int c = 0;
    if (tmp == dp[j]) c += cnt[j];                       // Transition from dp[j]
    if (tmp == dp[j - v[i]] + w[i]) c += cnt[j - v[i]];  // Transition from dp[j-v[i]]
    dp[j] = tmp;
    cnt[j] = c;
  }
}
int max = 0;  // Find the optimal solution
for (int i = 0; i <= V; i++) {
  max = std::max(max, dp[i]);
}
int res = 0;
for (int i = 0; i <= V; i++) {
  if (dp[i] == max) {
    res += cnt[i];  // Sum the number of optimal solutions
  }
}

The kth Best Knapsack Solution

Ordinary 0-1 knapsack asks for the optimal solution. By slightly modifying the ordinary knapsack DP and adding one dimension to record the first k solutions for the current state, we obtain an algorithm for the $k$th best solution to 0-1 knapsack． Specifically, $\mathit{dp_{i,j,k}}$ records the $k$th largest value sum obtainable from the first $i$ items when the selected items have total volume $j$. This state can be understood as extending ordinary 0-1 knapsack's $\mathit{dp_{i,j}}$, which records only one value, to an ordered sequence of optimal values. The ordinary transition is $\mathit{dp_{i,j}}=\max(\mathit{dp_{i-1,j}},\mathit{dp_{i-1,j-v_{i}}}+w_{i})$. Now we merge the two decreasing sequences of length $k$, $\mathit{dp_{i-1,j}}$ and $\mathit{dp_{i-1,j-v_{i}}}+w_{i}$, retaining the first $k$ largest values in $\mathit{dp_{i,j}}$. This uses a two-pointer method with complexity $O(k)$, giving an overall time complexity of $O(nmk)$. The first dimension can be compressed just as in ordinary knapsack, giving space complexity $O(mk)$．

memset(dp, 0, sizeof(dp));
int i, j, p, x, y, z;
scanf("%d%d%d", &n, &m, &K);
for (i = 0; i < n; i++) scanf("%d", &w[i]);
for (i = 0; i < n; i++) scanf("%d", &c[i]);
for (i = 0; i < n; i++) {
  for (j = m; j >= c[i]; j--) {
    for (p = 1; p <= K; p++) {
      a[p] = dp[j - c[i]][p] + w[i];
      b[p] = dp[j][p];
    }
    a[p] = b[p] = -1;
    x = y = z = 1;
    while (z <= K && (a[x] != -1 || b[y] != -1)) {
      if (a[x] > b[y])
        dp[j][z] = a[x++];
      else
        dp[j][z] = b[y++];
      if (dp[j][z] != dp[j][z - 1]) z++;
    }
  }
}
printf("%d\n", dp[m][K]);

References and Notes

• Nine Lectures on the Knapsack Problem - Cui Tianyi．