Translation Notice
This article was machine-translated using DeepSeek-R1.

• Original Version: Authored in Chinese by myself
• Accuracy Advisory: Potential discrepancies may exist between translations
• Precedence: The Chinese text shall prevail in case of ambiguity
• Feedback: Technical suggestions regarding translation quality are welcomed

Preface

The Knapsack Problem is a classic dynamic programming problem with practical significance.

0-1 Knapsack

Luogu P2871 [USACO07DEC] Charm Bracelet S
AtCoder Educational DP Contest D - Knapsack 1
There are $n$ items and a knapsack with total capacity $W$. The $i$-th item has weight $w_i$ and value $v_i$. Determine which items to select such that the total weight does not exceed the capacity while maximizing the total value.

This is the fundamental 0-1 Knapsack Problem (each item can be chosen either 0 or 1 times). Let’s explore its solution.

Let $f_{i,j}$ denote the maximum total value achievable by considering the first $i$ items with a knapsack capacity of $j$. The final answer is $f_{n,W}$, and the state transition equation is:

By incrementally increasing $i$ and expanding the problem scale, we can solve it. Both time and space complexity are $\mathcal O(nW)$.
In practice, $\mathcal O(nW)$ space may cause MLE. Hence, we optimize by reusing arrays or using rolling tables.

Compress the first dimension of $f$, resulting in:

Now space complexity reduces to $\mathcal O(W)$.
Remember to iterate $j$ in reverse order to prevent overlapping transitions. Reference code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <cstdio>
#define setmax(x, y) if(x < y) x = y
using namespace std;

int f[12881];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    while(n--)
    {
        int w, v;
        scanf("%d%d", &w, &v);
        for(int i=m; i>=w; i--)
            setmax(f[i], f[i - w] + v);
    }
    printf("%d\n", f[m]);
    return 0;
}

A variant of 0-1 Knapsack is finding minimum remaining space, where the answer is $(total\ space - maximum\ occupied\ space)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <cstdio>
#define setmax(x, y) if(x < y) x = y
using namespace std;

int f[20005];

int main()
{
    int n, v;
    scanf("%d%d", &v, &n);
    while(n--)
    {
        int w;
        scanf("%d", &w);
        for(int i=v; i>=w; i--)
            setmax(f[i], f[i - w] + w);
    }
    printf("%d\n", v - f[v]);
    return 0;
}

Extension: Handling Larger $W$

AtCoder Educational DP Contest E - Knapsack 2
This problem is identical to standard 0-1 Knapsack but with constraints $n\le 100,W\le 10^9,v_i\le 10^3$.

Given $W\le 10^9$, storing such large arrays is impossible. We reverse the DP state: instead of tracking weight to maximize value, track value to minimize weight. Let $f_{i,j}$ denote the minimum capacity required to achieve total value $j$ using the first $i$ items. Since $\sum v_i\le 10^5$, the DP array size becomes manageable ($\approx10^7$). The state transition equation is:

The final answer is the maximum $j$ where $f_{n,j}\le W$. Optimizations include:

• Time: For each $i$, iterate $j$ only up to cumulative value $v_1+\dots+v_i$
• Space: Compress the first dimension and iterate $j$ in reverse

Optimized code:

 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
27

#include <cstdio>
#include <cstring>
using namespace std;

long long f[100005], t, tot, ans;

int main()
{
    int n, sz;
    scanf("%d%d", &n, &sz);
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    while(n--)
    {
        int w, v;
        scanf("%d%d", &w, &v);
        tot += v;
        for(int i=tot; i>=v; i--)
            if((t = f[i - v] + w) < f[i] && t <= sz)
            {
                f[i] = t;
                if(i > ans) ans = i;
            }
    }
    printf("%lld\n", ans);
    return 0;
}

Unbounded Knapsack

Luogu P1616 Crazy Herb Gathering
Similar to 0-1 Knapsack, but each item can be chosen infinitely.

The key difference lies in unlimited item usage. For DP state $f_{i,j}$:

Compare with 0-1 Knapsack’s transition:

By changing loop order (forward iteration), we achieve this. Don’t forget long long:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <cstdio>
#define setmax(x, y) if(x < y) x = y
using namespace std;

long long f[10000005];

int main()
{
    int sz, n;
    scanf("%d%d", &sz, &n);
    while(n--)
    {
        int w, v;
        scanf("%d%d", &w, &v);
        for(int i=w; i<=sz; i++)
            setmax(f[i], f[i - w] + v);
    }
    printf("%lld\n", f[sz]);
    return 0;
}

Bounded Knapsack

Luogu P1776 Treasure Screening
Each item has a maximum selection count $m_i$. Constraints: $n\le100,\sum m_i\le10^5,W\le 4\times10^4$.

Naive approach (convert to 0-1 Knapsack with $N=\sum m_i$) yields $\mathcal O(W\sum m_i)$ complexity. Optimize via binary splitting: decompose $m_i$ into binary components (e.g., $5=1+2+2$). This reduces time to $\mathcal O(W\sum\log m_i)$. Reference code using binary optimization:

 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
27

#include <cstdio>
#define maxw 40004
#define setmax(x, y) if(x < y) x = y
using namespace std;

int n, w, f[maxw];

inline void add(int a, int b) // a: value, b: weight
{
    for(int i=w; i>=b; i--)
        setmax(f[i], f[i - b] + a);
}

int main()
{
    scanf("%d%d", &n, &w);
    while(n--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        for(int i=0; (1<<i)<=c; i++)
            add(a << i, b << i), c -= 1 << i;
        if(c) add(a * c, b * c);
    }
    printf("%d\n", f[w]);
    return 0;
}

Hybrid Knapsack

Combine all three knapsack types. For example, Luogu P1833 Cherry Blossoms. Handle via conditional branches:

1
2
3
4
5
6
7
8

for (each item type) {
  if (0-1 knapsack)
    apply 0-1 code;
  else if (unbounded)
    apply unbounded code;
  else if (bounded)
    apply bounded code;
}

Alternatively, unify handling by setting selection limits:

• 0-1: $k_i=1$
• Unbounded: $k_i=\lceil\frac W{w_i}\rceil$

Summary

Comparison of three basic knapsack DP types:

Like this article? Please support with a 👍⭐💬!