Core Logic and Mathematical Principles
The knapsack problem is a classic example of a high-dimensional constrained combinatorial optimization problem. Its essence lies in how to achieve the optimal value of the objective function (total value) through a phased scan of discrete decisions (to select or not, how many to select) under a finite resource boundary (knapsack capacity $V$).
The mathematical essence of the three core knapsack models varies:
- 0-1 Knapsack: Each item is available only once. The decision has a dual nature, and the state transition relies on the pure history of the previous stage that is not contaminated by the current item.
- Unbounded Knapsack: Each item is available in unlimited quantities. The decision has a continuous nature, and the state transition relies on the latest state that has included the current item.
- Bounded Knapsack: Each item has a fixed count limit $C_i$. Direct brute-force splitting can lead to a complexity degradation to $O(V \sum C_i)$.
- Binary Splitting Optimization: Decompose the quantity $C_i$ into a combination of powers of 2 that sum to $C_i$: $1, 2, 4, \dots, 2^k, C_i - (2^{k+1} - 1)$. Since any integer less than or equal to $C_i$ can be uniquely represented by this base set, the bounded knapsack is mapped to a 0-1 knapsack containing $O(\log C_i)$ new items, reducing the overall complexity to $O(N \cdot V \log C)$.
- Monotonic Queue Optimization: For the transition equation $f[j] = \max_{0 \le k \le C_i} \{ f[j - k \cdot w_i] + k \cdot v_i \}$, group items by the remainder of their volume $w_i$ with respect to capacity using congruence grouping: $j = r + q \cdot w_i$ (where $0 \le r < w_i$). The equation transforms along the same remainder chain to:
$$f[r + q \cdot w_i] = \max_{q - C_i \le k \le q} \{ f[r + k \cdot w_i] - k \cdot v_i \} + q \cdot v_i$$
This is a standard sliding window maximum problem. By maintaining a monotonically decreasing sequence of $f[r + k \cdot w_i] - k \cdot v_i$ using a monotonic queue, the state transition time can be optimized to $O(1)$, reducing the global complexity to the limit of $O(N \cdot V)$.
State Design and Algorithm Derivation
After compressing space using a one-dimensional rolling array, the state space, transition equations, and loop sequences of various knapsack types exhibit a rigorous geometric logic:
1. 0-1 Knapsack
- Equation: $f[j] = \max(f[j], f[j - w_i] + v_i)$
- Loop Order: Outer loop iterates through items $i$ in ascending order, while the inner loop iterates through capacity $j$ in descending order (from $V$ down to $w_i$).
- Geometric Derivation: The descending order ensures that when calculating $f[j]$, the referenced predecessor state $f[j - w_i]$ has not yet been updated by the $i$-th round of items; it still represents the net value of the $(i-1)$-th stage, aligning with the constraint that each item can only be selected once.
2. Unbounded Knapsack
- Equation: $f[j] = \max(f[j], f[j - w_i] + v_i)$
- Loop Order: Outer loop iterates through items $i$ in ascending order, while the inner loop iterates through capacity $j$ in ascending order (from $w_i$ up to $V$).
- Geometric Derivation: The ascending order allows the current state to accumulate on the basis of already updated predecessor states $f[j - w_i]$ (i.e., it has already included at least one item $i$), perfectly mapping the infinite selection characteristic.
3. Bounded Knapsack Binary Splitting
- Derivation Process: Let the quantity of a certain item be $C$. Set $k = 1$, and if $C \ge k$, split out an independent new item with volume $k \cdot w$, value $k \cdot v$, while updating $C = C - k, k = k \times 2$. Repeat until $C < k$. If $C > 0$ at the end, package the remaining $C$ as a new item. Finally, run the standard 0-1 knapsack on all the split new items.
C++ Standard Source Code (NOIP Style)
The following source code provides an efficient one-dimensional implementation of 0-1 knapsack, unbounded knapsack, and bounded knapsack (binary splitting) within the same program.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXV = 20005; // For knapsack capacity
int f[MAXV];
// Structure for flattened items resulting from splitting in bounded knapsack
struct Item {
int w, v;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, max_v;
if (!(cin >> n >> max_v)) return 0;
vector<Item> items;
for (int i = 1; i <= n; ++i) {
int w, v, c, type;
cin >> w >> v >> c >> type; // type: 1->0-1, 2->unbounded, 3->bounded
if (type == 1) {
items.push_back({w, v});
}
else if (type == 2) {
// Unbounded knapsack will be processed separately in ascending order later; here for unified scheduling, it can be temporarily excluded from the 0-1 queue
// For high cohesion in competitive programming, it is common to handle all three types of knapsacks in the main loop
}
else if (type == 3) {
// Bounded knapsack: core logic for binary splitting
for (int k = 1; c >= k; k <<= 1) {
items.push_back({k * w, k * v});
c -= k;
}
if (c > 0) {
items.push_back({c * w, c * v});
}
}
}
// ==================== Unified descending drive for 0-1 knapsack & bounded knapsack (after splitting) ====================
for (const auto& item : items) {
for (int j = max_v; j >= item.w; --j) { // Critical pitfall: must be strictly in descending order, otherwise it degenerates into unbounded knapsack
f[j] = max(f[j], f[j - item.w] + item.v);
}
}
// ==================== Independent ascending drive for unbounded knapsack (assuming a group of unbounded knapsack items is read in separately) ====================
// This is only for demonstration: if the item is of unbounded knapsack type, the loop must be rewritten in ascending order
int comp_w = 5, comp_v = 10; // Simulating an unbounded knapsack item
for (int j = comp_w; j <= max_v; ++j) { // Ascending drive, allowing state self-contamination, accommodating multiple items
f[j] = max(f[j], f[j - comp_w] + comp_v);
}
cout << f[max_v] << "\n";
return 0;
}NOIP Practical Pitfall Guide
1. Incorrect Loop Direction for Capacity in 0-1 Knapsack One-Dimensional Compression
- Phenomenon: The loop for the capacity of the 0-1 knapsack is written as
for (int j = w[i]; j <= V; ++j). The code compiles, but the output is vastly incorrect. This is because when calculating later states (e.g., $f[2w_i]$), it reads the previously updated $f[w_i]$ from the same round, causing an item to be counted multiple times, effectively degrading the 0-1 knapsack into an unbounded knapsack. - Avoidance Method: Always remember the underlying update logic of the one-dimensional rolling array. 0-1 knapsack must be in descending order (from large to small), while unbounded knapsack must be in ascending order (from small to large).
2. Missing Remaining Tail in Bounded Knapsack Binary Splitting
- Phenomenon: During binary splitting, if the loop condition is incorrect or if, after exiting the loop, the remaining $C$ (i.e., $C > 0$ and $C < k$) is forgotten to be packed into the item set, it leads to a shrinkage of the original item total, resulting in an underestimated maximum value.
- Avoidance Method: After splitting, always follow up with
if (c > 0) items.push_back({c * w, c * v});as a rigorous checkpoint to ensure the original total is split without loss.
Classic NOIP/Luogu Problems
1. Luogu P1776 Treasure Selection
- Problem Description: Given $N$ types of treasures, each with a value $v_i$, weight $w_i$, and quantity $m_i$. Now there is a knapsack with a weight limit of $W$, find the maximum total value that can be packed without exceeding the weight limit. $W \le 40000, N \le 100, m_i \le 100000$.
- Problem Essence and Solution Idea: A standard bounded knapsack problem. Since the quantity $m_i$ of a single type of item is extremely high, brute-force decomposition leads to a complexity of $O(W \sum m_i)$, which can cause a complete collapse.
- Core Idea: Use binary splitting. Perform bitwise splitting on the quantity $m_i$ of each treasure, transforming it into $\log m_i$ independent 0-1 knapsack items. After splitting, the total number of items reduces to $N \log M \approx 100 \times 17 \approx 1700$ items. Running standard one-dimensional reverse 0-1 knapsack state transitions on these 1700 new items results in approximately $1.7 \times 10^3 \times 4 \times 10^4 = 6.8 \times 10^7$ execution times, easily solvable within 1 second.
2. Luogu P1616 Crazy Herb Picking
- Problem Description: Given a total knapsack capacity $T$ and $M$ types of herbs, each of which can be picked without restriction. Given the picking time $t_i$ and value $v_i$ of each herb, find the maximum total value that can be obtained within the specified time. $T \le 10^7, M \le 10^4$.
- Problem Essence and Solution Idea: An extreme space and time squeezing problem for unbounded knapsack.
- Core Idea: Each item is available in unlimited quantities, and the state transition equation is structurally similar to that of the 0-1 knapsack, but the direction of space iteration must switch to ascending order.
- Critical Special Case: The data range of this problem is extremely malicious ($T \le 10^7$). If a two-dimensional state array is defined, it will explode in memory. The size of the one-dimensional state array
fmust be set to the order of $10^7$. Additionally, since value accumulation may severely exceed the limit of 32-bit integers, thefarray type and the variable storing the final answer must be declared aslong long, otherwise, at large data points, integer overflow will directly turn it into a negative number.