Skip to content

Knapsack DP

Prerequisites: Introduction to Dynamic Programming.

Introduction

Before delving into "knapsack DP", let's first look at the following example problem:

「USACO07 DEC」Charm Bracelet

Problem summary: There are \(n\) items and a knapsack with capacity \(W\). Each item has two attributes: weight \(w_{i}\) and value \(v_{i}\). Select some items to put into the knapsack such that the total value of the items in the knapsack is maximized, and the total weight does not exceed the knapsack's capacity.

In the above problem, since each item can only be in one of two states (taken or not taken), corresponding to \(0\) and \(1\) in binary, such problems are called "0-1 knapsack problems".

0-1 Knapsack

Explanation

The known conditions in the problem are the weight \(w_{i}\) and value \(v_{i}\) of the \(i\)-th item, and the total capacity \(W\) of the knapsack.

Define the DP state \(f_{i,j}\) as the maximum total value achievable with a knapsack of capacity \(j\), considering only the first \(i\) items.

Consider the transition. Suppose we have already processed all states for the first \(i-1\) items. For the \(i\)-th item, if we do not put it into the knapsack, the remaining capacity of the knapsack remains unchanged, and the total value of items in the knapsack also remains unchanged. Thus, the maximum value in this case is \(f_{i-1,j}\). If we put it into the knapsack, the remaining capacity decreases by \(w_{i}\), and the total value increases by \(v_{i}\). Hence, the maximum value in this case is \(f_{i-1,j-w_{i}}+v_{i}\).

From this, we derive the state transition equation:

\[ f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i}) \]

If we directly use a two-dimensional array to record the states, it may cause MLE. We can consider optimizing it using a rolling array.

Since only \(f_{i-1}\) affects \(f_i\), we can remove the first dimension and use \(f_{i}\) to represent the maximum value when processing the current item with knapsack capacity \(i\). This yields the following equation:

\[ f_j=\max \left(f_j,f_{j-w_i}+v_i\right) \]

It is essential to remember and understand this transition equation, as most knapsack problem transition equations are derived from it.

Implementation

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

1
2
3
4
5
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]]);
// Derived from f[i][l + w[i]] = max(max(f[i - 1][l + w[i]], f[i - 1][l] + w[i]),
// f[i][l + w[i]]);

1
2
3
4
5
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]])
# Derived from f[i][l + w[i]] = max(max(f[i - 1][l + w[i]], f[i - 1][l] + w[i]),
# f[i][l + w[i]])

What is wrong with this code? The enumeration order is incorrect.

Observing the code carefully, we can see: for the current 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 allowing item \(i\) to be placed into the knapsack multiple times, which contradicts the problem statement. (In fact, this is the solution for the unbounded knapsack problem.)

To avoid this, we can change the enumeration order from \(W\) down to \(w_{i}\). This ensures that \(f_{i,j}\) is always updated before \(f_{i,j-w_{i}}\), preventing the above error.

Thus, the actual core code is:

1
2
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]);

1
2
3
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])
Example Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#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 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 equation
  cout << f[W];
  return 0;
}

Unbounded Knapsack

Explanation

The unbounded knapsack model is similar to the 0-1 knapsack, with the only difference being that an item can be selected an unlimited number of times, rather than just once.

We can draw inspiration from the 0-1 knapsack approach for state definition: let \(f_{i,j}\) be the maximum value achievable with a knapsack of capacity \(j\), considering only the first \(i\) items.

Note that although the definition is similar to the 0-1 knapsack, the state transition equation is different.

Process

A naive approach is to enumerate how many times the \(i\)-th item is selected for transition. This yields a time complexity of \(O(n^3)\).

The state transition equation is:

\[ f_{i,j}=\max_{k=0}^{+\infty}(f_{i-1,j-k\times w_i}+v_i\times k) \]

Consider a simple optimization. It can be observed that for \(f_{i,j}\), it suffices to transition from \(f_{i,j-w_i}\). Therefore, the state transition equation becomes:

\[ f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i) \]

The reason is that when we transition this way, \(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 the number of times the \(i\)-th item is selected. In other words, we reuse previous enumeration processes through the property of optimal substructure, optimizing the enumeration complexity.

Similar to the 0-1 knapsack, we can remove the first dimension to optimize space complexity. If you understand the optimization method for the 0-1 knapsack, it is not difficult to see that the compressed loop should be forward (as in the erroneous optimization mentioned above).

「Luogu P1616」Crazy Herb Gathering

Problem summary: There are \(n\) types of items and a knapsack with capacity \(W\). Each item has two attributes: weight \(w_{i}\) and value \(v_{i}\). Select some items to put into the knapsack such that the total value of the items in the knapsack is maximized, and the total weight does not exceed the knapsack's capacity.

Example Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#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 state transition equation
  cout << f[W];
  return 0;
}

Bounded Knapsack

Bounded knapsack is also a variant of the 0-1 knapsack. The difference from the 0-1 knapsack is that each item has \(k_i\) copies, rather than just one.

A straightforward idea is to treat "selecting the \(i\)-th item \(k_i\) times" as equivalent to "having \(k_i\) identical items, each selected once". This transforms the problem into a 0-1 knapsack model, and the method described above can be applied. The state transition equation is:

\[ f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,j-k\times w_i}+v_i\times k) \]

Time complexity: \(O(W\sum_{i=1}^nk_i)\).

Core Code 
1
2
3
4
5
6
7
8
for (int i = 1; i <= n; i++) {
  for (int weight = W; weight >= w[i]; weight--) {
    // One more loop for 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 optimization. We still aim to transform the bounded knapsack into a 0-1 knapsack model.

Explanation

Clearly, the \(O(nW)\) part of the complexity cannot be further optimized; we can only work on the \(O(\sum k_i)\) part. For convenience, let \(A_{i,j}\) represent the \(j\)-th item split from the \(i\)-th type of item.

In the naive approach, \(\forall j\le k_i\), \(A_{i,j}\) represents the same item. The main reason for inefficiency is the large amount of redundant work. For example, we considered both "select \(A_{i,1}\) and \(A_{i,2}\) together" and "select \(A_{i,2}\) and \(A_{i,3}\) together", which are completely equivalent. We perform such redundant work many times. Thus, optimizing the splitting method becomes the key to solving the problem.

Process

We can use "binary grouping" to make the splitting method more elegant.

Specifically, let \(A_{i,j}\left(j\in\left[0,\lfloor \log_2(k_i+1)\rfloor-1\right]\right)\) represent a large item "bundled" from \(2^{j}\) individual items. If \(k_i+1\) is not a power of two, we need to add an extra large item "bundled" from \(k_i-2^{\lfloor \log_2(k_i+1)\rfloor-1}\) individual items to make up the difference.

Examples:

  • \(6=1+2+3\)
  • \(8=1+2+4+1\)
  • \(18=1+2+4+8+3\)
  • \(31=1+2+4+8+16\)

Clearly, with this splitting method, we can represent any selection equivalent to \(\le k_i\) items. After splitting each item type in this way, we can solve it using the 0-1 knapsack method.

Time complexity: \(O(W\sum_{i=1}^n\log_2k_i)\)

Implementation

Binary Grouping Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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

Refer to Monotone Queue/Stack Optimization.

Exercise: 「Luogu P1776」Treasure Screening_NOI Guide 2010 Improvement (02)

Mixed Knapsack

Mixed knapsack combines the three types of knapsack problems mentioned above: some items can be taken only once, some can be taken unlimited times, and some can be taken at most \(k\) times.

Such problems may seem intimidating, but as long as you grasp the core ideas of the previous knapsack types and combine them, they become manageable. Pseudocode is given below:

1
2
3
4
5
6
7
8
for (each item type) {
  if (it is a 0-1 knapsack)
    apply 0-1 knapsack code;
  else if (it is an unbounded knapsack)
    apply unbounded knapsack code;
  else if (it is a bounded knapsack)
    apply bounded knapsack code;
}

Example

「Luogu P1833」Cherry Blossoms

There are \(n\) types of cherry blossom trees and a time length \(T\). Some cherry blossom trees can only be viewed once, some at most \(A_{i}\) times, and some an unlimited number of times. Each cherry blossom tree has an aesthetic value \(C_{i}\). Determine which cherry blossom trees to view within time \(T\) to maximize the total aesthetic value.

Core Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
for (int i = 1; i <= n; i++) {
  if (cnt[i] == 0) {  // If there is no limit on quantity, use unbounded knapsack core code
    for (int weight = w[i]; weight <= W; weight++) {
      dp[weight] = max(dp[weight], dp[weight - w[i]] + v[i]);
    }
  } else {  // If the item is limited, use bounded knapsack core code, which can also handle 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

Two-dimensional Cost Knapsack

「Luogu P1855」Squeeze kkksc03

There are \(n\) tasks to complete. Completing the \(i\)-th task takes \(t_i\) minutes and costs \(c_i\) dollars.

Now, there are \(T\) minutes and \(W\) dollars to handle these tasks. Determine the maximum number of tasks that can be completed.

This problem is clearly a 0-1 knapsack problem, but with a twist: selecting an item consumes two types of costs (money and time). We simply add another dimension to the state to store the second cost.

Note that adding another dimension for the item index is not appropriate here, as it may cause MLE.

Implementation

1
2
3
4
for (int k = 1; k <= n; k++)
  for (int i = m; i >= mi; i--)    // Enumerate over money
    for (int j = t; j >= ti; j--)  // Enumerate over time
      dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1);

1
2
3
4
for k in range(1, n + 1):
    for i in range(m, mi - 1, -1):  # Enumerate over money
        for j in range(t, ti - 1, -1):  # Enumerate over time
            dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1)

Group Knapsack

「Luogu P1757」Group Knapsack

There are \(n\) items and a knapsack with capacity \(m\). The \(i\)-th item has value \(w_i\) and volume \(v_i\). Additionally, each item belongs to a group, and at most one item can be selected from each group. Find the maximum total value the knapsack can hold.

How to approach this? Essentially, it changes from "choose one item from all items" to "choose one item from the current group". Thus, we perform a 0-1 knapsack for each group.

Regarding storage: we can use \(t_{k,i}\) to represent the index of the \(i\)-th item in the \(k\)-th group, and \(\mathit{cnt}_k\) to represent the number of items in the \(k\)-th group.

Implementation

1
2
3
4
5
6
for (int k = 1; k <= ts; k++)          // Iterate over each group
  for (int i = m; i >= 0; i--)         // Iterate over knapsack capacity
    for (int j = 1; j <= cnt[k]; j++)  // Iterate over each item in the group
      if (i >= w[t[k][j]])             // If capacity is sufficient
        dp[i] = max(dp[i],
                    dp[i - w[t[k][j]]] + c[t[k][j]]);  // Transition like 0-1 knapsack

1
2
3
4
5
6
7
for k in range(1, ts + 1):  # Iterate over each group
    for i in range(m, -1, -1):  # Iterate over knapsack capacity
        for j in range(1, cnt[k] + 1):  # Iterate over each item in the group
            if i >= w[t[k][j]]:  # If capacity is sufficient
                dp[i] = max(
                    dp[i], dp[i - w[t[k][j]]] + c[t[k][j]]
                )  # Transition like 0-1 knapsack

Important: The order of loops must not be mistaken to ensure correctness.

Dependent Knapsack

「Luogu P1064」Jinming's Budget Plan

Jinming has \(n\) yuan and wants to buy \(m\) items. The price of the \(i\)-th item is \(v_i\), and its importance is \(p_i\). Some items are attachments belonging to a main item; to buy such an item, its main item must be purchased.

The goal is to maximize the sum of \(v_i \times p_i\) for all purchased items.

Consider case analysis. For a main item and its attachments, there are several possibilities: buy only the main item, or buy the main item plus some attachments. Since only one of these possibilities can be chosen, this can be treated as a group knapsack.

If it is a collection of multiway trees, compute the sets for child nodes first, and finally compute the set for the parent node.

Generalized Items Knapsack

In this type of knapsack, there is no fixed cost or value; its value depends on the cost allocated to it. In a knapsack problem with capacity \(V\), when allocated cost \(v_i\), the value obtained is \(h\left(v_i\right)\). In this case, replace the fixed value with a function reference.

Miscellaneous

Minor Optimizations

Based on the greedy principle: when costs are the same, keep only the item with the highest value; when values are the same, keep only the item with the lowest cost; when there are two items \(i,j\) such that \(i\) has higher value than \(j\) and lower cost than \(j\), keep only \(i\).

Knapsack Problem Variants

Outputting the Solution

Outputting the solution essentially involves recording how a particular state in the knapsack was derived. We can use \(g_{i,v}\) to indicate whether the \(i\)-th item was selected when it occupies space \(v\). Then, during transition, record which strategy (select or not select) was used. Pseudocode for output:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int v = V;  // Record current storage space

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

Counting the Number of Solutions

For a given knapsack capacity, item costs, and other constraints, count the total number of ways to fill the knapsack to a certain capacity.

This variant simply changes maximizing to summing.

For example, the transition equation for the 0-1 knapsack becomes:

\[ \mathit{dp}_i=\sum(\mathit{dp}_i,\mathit{dp}_{i-c_i}) \]

Initial condition: \(\mathit{dp}_0=1\)

Because when capacity is \(0\), there is one solution: take nothing.

Counting Optimal Solutions

To count the number of optimal solutions, we slightly modify the definition of the \(\mathit{dp}\) array in the 0-1 knapsack. DP state \(f_{i,j}\) is the maximum total value achievable with a knapsack of capacity \(j\) exactly full, considering only the first \(i\) items.

After this modification, each DP state can be associated with a \(g_{i,j}\) representing the number of solutions.

\(f_{i,j}\) represents the maximum value when considering only the first \(i\) items and the knapsack volume is exactly \(j\).

\(g_{i,j}\) represents the number of solutions when considering only the first \(i\) items and the knapsack volume is exactly \(j\).

Transition equations:

If \(f_{i,j} = f_{i-1,j}\) and \(f_{i,j} \neq f_{i-1,j-v}+w\), it means not selecting the item is better. The count is transferred from \(g_{i-1,j}\).

If \(f_{i,j} \neq f_{i-1,j}\) and \(f_{i,j} = f_{i-1,j-v}+w\), it means selecting the item is better. The count is transferred from \(g_{i-1,j-v}\).

If \(f_{i,j} = f_{i-1,j}\) and \(f_{i,j} = f_{i-1,j-v}+w\), it means both selecting and not selecting yield the optimal solution. The count is transferred from both \(g_{i-1,j}\) and \(g_{i-1,j-v}\).

Initial conditions:

1
2
3
4
5
memset(f, 0xcf, sizeof(f));
// Since we are maximizing, initialize to negative infinity to avoid transitions from unfilled states
// If minimizing, initialize to positive infinity 0x3f
f[0] = 0;
g[0] = 1;  // Taking nothing is one solution

Because the knapsack might not be fully filled at maximum volume, the optimal solution is not necessarily \(f_{m}\).

Finally, we find the value of the optimal solution and sum all \(g_{j}\) that achieve the optimal solution.

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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];                       // If transition from dp[j]
    if (tmp == dp[j - v[i]] + w[i]) c += cnt[j - v[i]];  // If 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 k-th Best Solution for Knapsack

The ordinary 0-1 knapsack seeks the optimal solution. By slightly modifying the ordinary knapsack DP method and adding a dimension to record the top k solutions for the current state, we can obtain an algorithm for the k-th best solution of the 0-1 knapsack. Specifically: \(\mathit{dp_{i,j,k}}\) records the k-th largest value achievable with total volume \(j\) from the first \(i\) items. This state can be seen as extending the ordinary 0-1 knapsack's \(\mathit{dp_{i,j}}\), which records a single value, to record an ordered sequence of top k solutions. During transition, the ordinary knapsack's optimal solution is \(\mathit{dp_{i,j}}=\max(\mathit{dp_{i-1,j}},\mathit{dp_{i-1,j-v_{i}}}+w_{i})\). Now, we need to merge the two decreasing sequences \(\mathit{dp_{i-1,j}}\) and \(\mathit{dp_{i-1,j-v_{i}}}+w_{i}\), each of size \(k\), and keep the top k values in \(\mathit{dp_{i,j}}\). This step uses the two-pointer method with complexity \(O(k)\), yielding an overall time complexity of \(O(nmk)\). Space-wise, like the ordinary knapsack, the first dimension can be compressed, resulting in complexity \(O(mk)\).

Example HDU 2639 Bone Collector II

Find the strictly k-th best solution for the 0-1 knapsack. \(n \leq 100,v \leq 1000,k \leq 30\)

Implementation 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用