Three Types of Knapsack Problems

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.

knapsack

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

$$ f_{i,j}=\begin{cases} 0 & (i=0/j=0) \\ \max(f_{i-1,j},f_{i-1,j-w_i}+v_i) & (i>0,j\ge w_i) \end{cases} $$

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.

$$ f_j=\max(f_j,f_{j-w_i}+v_i) $$

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$.

$$ f_{i,j}=\begin{cases} +\infin & (i=0,j\ne0) \\ 0 & (i\ge 0,j=0) \\ \min(f_{i-1,j},f_{i-1,j-v_i}+w_i) & (i>0,j>0) \end{cases} $$

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.

$$ f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i) $$$$ \begin{aligned} 0\text{-}1: & \max(f_{i-1,j},f_{i-1,j-w_i}+v_i) \\ \text{Unbounded}: & \max(f_{i-1,j},f_{i,j-w_i}+v_i) \end{aligned} $$

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:

Aspect	0-1 Knapsack	Unbounded Knapsack	Bounded Knapsack
Scenario	Each item once	Unlimited items	Limited items
State Transition¹	$\max(f_j,f_{j-w_i}+v_i)$	$\max(f_j,f_{j-w_i}+v_i)$	Similar to 0-1
Time Complexity²	$\mathcal O(nW)$	$\mathcal O(nW)$	$\mathcal O(W\sum\log k_i)$
Space Complexity	$\mathcal O(W)$	$\mathcal O(W)$	$\mathcal O(W)$
Coding Difficulty	Low	Low	Medium

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

Compressed $f_j$; 0-1 uses reverse iteration, unbounded uses forward ↩︎
Unbounded uses optimized complexity; bounded uses binary optimization ↩︎