【学习笔记】子集和问题

零、问题引入

子集和问题 $\text{Subset-sum Problem (SSP)}$，其意在求解关于 $\xi (S)=\{{\sum }_{i\in T}{w}_i|T\subseteq S\}$ 的信息。

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

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

壹、平衡

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

贰、平衡算法

设可重集 $\mathbb{U}=\{w_i\}$，记 $A=[-W,0]\cap \mathbb{U},B=\mathbb{U}\setminus A$ 。设 $A=\{a_1,\dots ,a_{|A|}\},B=\{b_1,\dots ,b_{|B|}\}$ 。

Definition 2. 对于 $s\in [0,|A|],t\in [0,|B|]$ 和 $\mu \in (C-W,C+W]$，定义
$$\begin{gathered} f_{s,t}(\mu )=\left[\exists S,\sum _{i\in S}{w}_i=\mu \right] \\ \begin{array}{rl}\text{s.t.}& S\subseteq \{a_1,\dots ,a_s\}\cup \{b_1,\dots ,b_s\}\\ & S\text{ forms a balanced filling}\end{array} \end{gathered}$$

其中 $\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(\mu )=\min \{s:f_{s,t}(\mu )=1\}$$

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

定义 $s_t(\mu )=|A|+1$ 若不存在对应的 $s$ 。于是有如下伪代码：
$$\begin{array}{rl}& \text{Algorithm }\text{balsub}\\ 1& \text{for }\mu \leftarrow C-W+1\text{ to }C+W\text{ do }\\ 2& s_0(\mu )\leftarrow |A|+1\\ 3& s_0(0)\leftarrow 0\\ 4& \text{for }t\leftarrow 1\text{ to }|B|\text{ do}\\ 5& \text{for }\mu \leftarrow C-W+1\text{ to }C+W\text{ do}\\ 6& s_t(\mu )\leftarrow s_{t-1}(\mu )\\ 7& \text{for }\mu \leftarrow C-W+1\text{ to }C\text{ do }\\ 8& {\mu }^{\prime }\leftarrow \mu +b_t\\ 9& s_t({\mu }^{\prime })\leftarrow \min \{s_t({\mu }^{\prime }),s_{t-1}(\mu )\}\\ 10& \text{for }\mu \leftarrow C+W\text{ downto }C+1\text{ do}\\ 11& \text{for }j\leftarrow s_t(\mu )+1\text{ to }{s}_{t-1}(\mu )\text{ do}\\ 12& {\mu }^{\prime }\leftarrow \mu +a_j\\ 13& s_t({\mu }^{\prime })\leftarrow \min \{s_t({\mu }^{\prime }),j\}\end{array}$$

第 $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\in \xi (\mathbb{U})\}=\max \{z:z⩽C,s_{|B|}(\mu )\ne |A|+1\}$，或者 $\min \{|i-C|:i\in \xi (\mathbb{U})\}=\min \{i:s_{|B|}(C\pm i)\ne |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.