P15562 [CCPC 2025 Harbin Site] 0/1 Knapsack

The 0/1 knapsack problem is a classic combinational optimization problem in algorithm competitions. Little w has learned a greedy algorithm to solve this problem. The definition of the 0/1 knapsack problem and Little w's greedy algorithm are as follows. $\textbf{0/1 Knapsack Problem}$: Given $n$ items. The weights of the items are positive integers $w_1,w_2,\ldots,w_n$, and the values of the items are positive integers $v_1,v_2,\ldots,v_n$. You are also given the knapsack capacity $W$. You need to choose $x_1,x_2,\ldots,x_n$ ($\forall 1 \le i \le n$, $x_i \in \{0,1\}$), such that: $$ \sum_{i=1}^n w_ix_i \le W $$ and maximize: $$ V = \sum_{i=1}^n v_ix_i $$ $\textbf{Greedy Algorithm}$: 1. Sort the $n$ items in descending order of $\frac{v_i}{w_i}$. If $\frac{v_i}{w_i}$ is the same, sort by $w_i$ in descending order. 2. Set an initial variable $W_0$ to $0$, and enumerate $i$ from $1$ to $n$. If $W_0 + w_i \le W$, then set $x_i \leftarrow 1, W_0 \leftarrow W_0 + w_i$; otherwise set $x_i \leftarrow 0$. 3. After the enumeration, you obtain the required $x_1,x_2,\ldots,x_n$ and $V$. Of course, you know this algorithm is incorrect, but Little w does not believe it. Even if you give Little w some counterexamples, Little w still thinks that under many different $W$, this algorithm can still produce the optimal $V$. So now you want to construct a set of $w_1,w_2,\ldots,w_n$ and $v_1,v_2,\ldots,v_n$ such that: 1. $\forall 2 \le W \le W_{lim}$ ($W_{lim}$ is a given constant), Little w's algorithm cannot obtain the optimal $V$. 2. Under condition $1$, make $n$ as small as possible. 3. Under conditions $1,2$, make $\max(w_1,w_2,\ldots,w_n)$ as small as possible. 4. Under conditions $1,2,3$, make $\max(v_1,v_2,\ldots,v_n)$ as small as possible. Now you need to construct a 0/1 knapsack instance that satisfies the requirements above to convince Little w. Can you do it? If there are multiple construction methods, you may output any one.

The input consists of one line containing one integer $W_{lim}$ ($2 \le W_{lim} \le 5 \times 10^3$), representing the upper bound of $W$.

The first line contains one integer $n$ ($1 \le n \le 10^4$), representing the number of items in the constructed 0/1 knapsack instance. The second line outputs $n$ integers $w_1,w_2,\ldots,w_n$ ($1 \le w_i \le W_{lim}$), representing the item weights. The third line outputs $n$ integers $v_1,v_2,\ldots,v_n$ ($1 \le v_i \le 10^9$), representing the item values. It can be proven that under the given problem and input constraints, a solution within the given constraints always exists.

Translated by ChatGPT 5