零、问题引入

子集和问题 $\text{Subset-sum Problem (SSP)}$，其意在求解关于 ξ ( S ) = { ∑ i ∈ T w i    ∣    T ⊆ S } \xi(S)=\{\sum_{i\in T}w_i\;|\;T\subseteq S\} ξ(S)={∑i∈T​wi​∣T⊆S} 的信息。

如果求解的是 $\xi (S)$ 某个值附近的信息，根据背包过程，我们可以总在该值附近浮动。这被称为 $\text{balancing}$ 。

利用它，我们可以 $\mathcal{O}(nW)$ 求解某个值的最近邻信息，比如 max ⁡ { i    ∣    i ∈ ξ ( S ) ,    i ⩽ C } \max\{i\;|\;i\in\xi(S),\;i\leqslant C\} max{i∣i∈ξ(S),i⩽C}，其中 W = max ⁡ { ∣ w i ∣ } W=\max\{|w_i|\} W=max{∣wi​∣} 。

壹、平衡

Theorem. 可以在 $\mathcal{O}(n)$ 时间内得到 $C\in [0,W)$ 的问题。

Proof. 若 $C<0$ 则所有数取反（我们仍求出了 $C$ 的最近邻信息）；不妨设 $C⩾0$ 。在 $w_i>0$ 上，贪心取极大子集 $S$ 满足 ${\sum }_{i\in S}{w}_i⩽C$，将 $S$ 内元素取反、将 $C$ 变为 $C-{\sum }_{i\in S}{w}_i$ 。根据流程，若有 $i\notin S$ 满足 $w_i>0$ 则 $C<w_i⩽W$，否则 ${\sum }_{i\in S}{w}_i$ 就是 $C$ 的最近邻。$■$

下文可能将 $x$ 视作解向量。

Definition 1. 平衡填充（$\text{balanced filling}$）$x$ 是从 $x_j=0(j=1,\dots ,n)$ 开始，进行若干 平衡调整 得到的，具体而言：

• $x_j=0(j=1,\dots ,n)$ 是平衡填充。
• 平衡加. 对于平衡填充 $x$ 满足 $w\cdot x⩽C$，取 $x_t=0(w_t⩾0)$，令 $x_t=1$ 得到的 $x^{\prime }$ 是平衡填充。
• 平衡减. 对于平衡填充 $x$ 满足 $w\cdot x>C$，取 $x_s=0(w_s<0)$，令 $x_s=1$ 得到的 $x^{\prime }$ 是平衡填充。

Proposition. 对于 $C$ 的（任意一侧）最近邻，存在解 $x$ 是平衡填充。

Proof. 显然。以负方向最近邻为例。从 $x_j=0(j=1,\dots ,n)$ 开始，不断平衡加，总重超过 $C$ 就平衡减。$■$

Corollary. 平衡填充总满足 $C-W<w\cdot x⩽C+W$ 。

贰、平衡算法

设可重集 U = { w i } \Bbb U=\{w_i\} U={wi​}，记 $A=[-W,0]\cap \mathbb{U},B=\mathbb{U}\setminus A$ 。设 A = { a 1 , … , a ∣ A ∣ } ,    B = { b 1 , … , b ∣ B ∣ } A=\{a_1,\dots,a_{|A|}\},\;B=\{b_1,\dots,b_{|B|}\} A={a1​,…,a∣A∣​},B={b1​,…,b∣B∣​} 。

Definition 2. 对于 $s\in [0,|A|],t\in [0,|B|]$ 和 $\mu \in (C-W,C+W]$，定义
f s , t ( μ ) = [ ∃ S ,    ∑ i ∈ S w i = μ ] s.t. S ⊆ { a 1 , … , a s } ∪ { b 1 , … , b s } S  forms a balanced filling f_{s,t}(\mu)=\left[\exist S,\;\sum_{i\in S}w_i=\mu\right]\\

fs,t​(μ)=[∃S,i∈S∑​wi​=μ]s.t.​S⊆{a1​,…,as​}∪{b1​,…,bs​}S forms a balanced filling​

其中 $\text{balanced filling}$ 是平衡填充。虽然前面是用 “向量” 的口吻定义的，换成集合想必也不会引起误会。

显然只需考虑 $f_{s,t}(\mu )=1$ 的三元组 $(s,t,\mu )$ 。注意到 $t,\mu$ 固定时 $s$ 越小越好。

Definition 3. 对于 $t\in [0,|B|]$ 和 $\mu \in (C-W,C+W]$，定义
s t ( μ ) = min ⁡ { s : f s , t ( μ ) = 1 } s_t(\mu)=\min\{s: f_{s,t}(\mu)=1\} st​(μ)=min{s:fs,t​(μ)=1}

对其进行 $\mathtt{d}\mathtt{p}$ 。按照 $t$ 从小到大的顺序，每次考虑是否进行平衡加和平衡减。

定义 $s_t(\mu )=|A|+1$ 若不存在对应的 $s$ 。于是有如下伪代码：
Algorithm  balsub 1 for   μ ← C − W + 1   to   C + W   do   2 s 0 ( μ ) ← ∣ A ∣ + 1 3 s 0 ( 0 ) ← 0 4 for   t ← 1   to   ∣ B ∣   do 5 for   μ ← C − W + 1   to   C + W   do 6 s t ( μ ) ← s t − 1 ( μ ) 7 for   μ ← C − W + 1   to   C   do   8 μ ′ ← μ + b t 9 s t ( μ ′ ) ← min ⁡ { s t ( μ ′ ) ,    s t − 1 ( μ ) } 10 for   μ ← C + W   downto   C + 1   do 11 for   j ← s t ( μ ) + 1   to   s t − 1 ( μ )   do 12 μ ′ ← μ + a j 13 s t ( μ ′ ) ← min ⁡ { s t ( μ ′ ) ,    j }

12345678910111213​Algorithm balsubfor μ←C−W+1 to C+W do s0​(μ)←∣A∣+1s0​(0)←0for t←1 to ∣B∣ dofor μ←C−W+1 to C+W dost​(μ)←st−1​(μ)for μ←C−W+1 to C do μ′←μ+bt​st​(μ′)←min{st​(μ′),st−1​(μ)}for μ←C+W downto C+1 dofor j←st​(μ)+1 to st−1​(μ) doμ′←μ+aj​st​(μ′)←min{st​(μ′),j}​​

第 $5–6$ 行是不进行平衡加。第 $7–11$ 行进行平衡加。第 $12–13$ 行在 $s_t(\mu )$ 对应的方案上做了平衡减。注意 $11$ 行处 $j=|A|+1$ 可能出现，此时转移应当被忽略。

最关键处在于第 $11$ 行的上界 $s_{t-1}(\mu )$ 。这是因为 $j>s_{t-1}(\mu )$ 时，与之等效的转移可以在 $s_{t-1}(\mu )$ 上完成。这直接使得第 $11$ 行的循环次数，对于每个 $\mu$，是 ${\sum }_t{s}_{t-1}(\mu )-s_t(\mu )=s_0(\mu )-s_{|B|}(\mu )⩽|A|$ 。因此总复杂度 $\mathcal{O}(nW)$ 。

通过该数组，我们可直接求出 max ⁡ { i : i ⩽ C ,    i ∈ ξ ( U ) } = max ⁡ { z : z ⩽ C ,    s ∣ B ∣ ( μ ) ≠ ∣ A ∣ + 1    } \max\{i:i\leqslant C,\;i\in\xi(\Bbb U)\}=\max\{z:z\leqslant C,\;s_{|B|}(\mu)\ne |A|+1\;\} max{i:i⩽C,i∈ξ(U)}=max{z:z⩽C,s∣B∣​(μ)​=∣A∣+1}，或者 min ⁡ { ∣ i − C ∣ : i ∈ ξ ( U ) } = min ⁡ { i : s ∣ B ∣ ( C ± i ) ≠ ∣ A ∣ + 1 } \min\{|i-C|:i\in\xi(\Bbb U)\}=\min\{i:s_{|B|}(C\pm i)\ne|A|+1\} min{∣i−C∣:i∈ξ(U)}=min{i:s∣B∣​(C±i)​=∣A∣+1} 。

叁、引用

D. Pisinger, Linear time algorithms for knapsack problems with bounded weights, Journal of Algorithms. 33 (1999) 1–14 10.1006/jagm.1999.1034.

Chao Xu, Subset sum through balancing, personal blog.