子集总和：将特殊情况减少为一般情况

Question

维基百科 将子集和问题描述为寻找给定整数多重集的子集，其总和为零。此外，它还指出，这相当于找到一个具有总和的子集 $s$ 对于任何给定的 $s$.

所以我认为，既然它们是等价的，那么任何一方都会减少。那个来自 $s$ 通过设置为零是微不足道的 $s = 0$. 。但我没能找到从零减少到 $s$, ， IE。给定一组整数 $A$,构造一组整数 $B$ 包含总和的子集 $s$ （对于任何 $s$），当且仅当存在子集 $A$ 总和为零。

你能给我一些指点吗？

Answer 1

实际上，您已经从特殊到一般减少了。通过设置$ s = 0 $，您基本上正在使用常规算法来解决特殊问题。

相反（即从一般到特殊的减少）：

假设您得到了一个集合$ s = {x_1， dots，x_n } $和一个数字$ k $，您必须确定是否有一些$ s $的子集，总计为$ k $。

现在，您要解决此问题，给定一种算法，您可以确定某些子集总和是否为$ 0 $。

现在，如果$ x_i gt 0 $，我们可以轻松减少：$ s'= {x_1，x_2， dots，x_n，-k } $。

$ s'$的子集的总和$ 0 $ iff $ s $具有$ k $的子集。

当我们可以为某些$ i $的某些$ x_i le 0 $带有$ x_i le 0 $时，就会发生问题。

我们可以假设$ k gt 0 $（为什么？）。

假设正$ x_i $的总和是$ p $，负$ x_i $是$ n $。

现在构造一个新集合$ s'= {y_1，y_2 dots，y_n } $

$ y_i = x_i + m $其中$ m = p + | n | + k $。

每个$ y_i gt 0 $。

现在在集合上运行零subset-sum算法

$ s' cup { - （k+m）} $

$ s' cup { - （k+2m）} $

$ s' cup { - （k+3m）} $

$ dots $

$ s' cup { - （k+nm）} $

很容易证明，如果$ s $具有sum $ k $的子集，那么上述至少一组的总和为零。

我将向您留下另一个方向的证明。

Answer 2

阿里亚巴塔的回答 可以通过利用以下事实来解决：我们可以将所有数字乘以一些大的数字 $c$, ，然后为每个数字添加一些小内容以充当“存在标签”，然后提供一些额外的数字，使我们能够达到零 如果 我们可以到达 $cK$ 没有他们。具体来说，我们将使用 $c=2(n+1)$ 1 作为存在标签。

给定一个例子 $(S = \{x_1, \点, x_n\}, K)$ 目标值的一般问题 $K$, ，我们将创建特定问题的实例（目标值为 0），其中包含：

• $Y = \{y_1, \点, y_n\}$, ， 在哪里 $y_i = 2(n+1)x_i + 1$.
• 号码 $z = -2K(n+1)-n$.
• $n-1$ 数字 1 的副本，称为“上拉”数字。

我假设 Aryabhatta 会这样做 $K$ 是积极的。（已经过去六年了，我来为读者解答一下他的练习：我们能做到这一点的原因是如果我们交换 全部 一般问题实例中的数字，包括 $K$, ，然后我们最终得到一个新的、等效的问题实例。这意味着解决正问题的算法$K$ 实例足以解决任何问题——用负数来解决实例 $K$, ，我们可以执行此符号交换，运行该算法，并将其答案作为原始问题的答案转发。当然如果 $K=0$ 那么我们根本不需要将一般情况转换为特殊情况！）

首先让我们展示一下 对一般问题的给定实例的“是”答案意味着对特殊问题的构造实例的“是”答案。 这里我们可以假设有一些解决方案 $\{x_{j_1}, \点, x_{j_m}\}$ 存在的普遍问题：也就是说，这个非空集合 $百万$ 数字总和为 $K$. 。那么如果我们取相应的 $y$-价值观 $\{y_{j_1}, \点, y_{j_m}\}$ 在我们对构造实例的解决方案中，它们的总和将为 $2K(n+1)+m$. 。然后我们可以选择包括 $-2K(n+1)-n$ 在解决方案中，我们得到总和 $m-n$. 。自从 $1 \le m \le n$, ，这在范围内 $[-n+1, 0]$, ，我们可以通过包含上拉数字的一些子集来成功地将其拉至 0。

现在让我们展示一下 对构造实例的“是”答案意味着对原始给定实例的“是”答案。 这就是乘法的地方 $2(n+1)$ 变得很重要——它使我们能够确定我们所包含的额外数字不会“做太多”。

这里我们可以假设有一些解决方案 $\{y_{j'_1}, \点, y_{j'_{m'}}\}$ 构造的实例存在：也就是说，这个非空集合 $m'$ 数字总和为 0。根据问题要求，该解至少包含一个要素。此外，它必须包含至少一个元素 $Y$, ，因为没有这个就不可能达到总数 0：如果仅存在上拉数字，则总和必然在范围内 $[1, n-1]$ （请注意，在这种情况下 最后一个 上拉数必须存在，且全部严格为正数，因此总和不能为0）；而如果解决方案仅包含 $z$ 和一些上拉数字，那么总数必然是负数，因为 $z = -2K(n+1)-n \le -n$ 上拉数字最多可以增加总和为 $n-1$.

现在假设矛盾解不包含 $z$. 。中的每个元素 $Y$ 由两个术语组成：的倍数 $2(n+1)$, ，以及+1“存在标签”。请注意，每个上的 +1 项 $n$ 要点 $Y$ 如果选择该元素，则总和增加 1，每个最多 $n-1$ 所选择的上拉数字，因此这 2 个源对任何解决方案贡献的总和至少为 1（因为我们在上一段中确定至少有一个元素 $Y$ 必须选择）并且最多 $n + n-1 = 2n-1$. 。特别是，这意味着这两组项的总和， 当取模时 $2(n+1)$, ，非零。假设解不包含 $z$, ，这个总和中唯一的其他组成部分是 $2(n+1)$ 由选定的成员贡献 $Y$, ，这不会影响取模时的总和值 $2(n+1)$. 。因此，当取模时，解中所有项的总和 $2(n+1)$, ，非零，意味着它不能等于目标总和 0，意味着它根本不可能是有效的解：我们发现了一个矛盾，这意味着它一定是 $z = -2K(n+1)-n$ 毕竟存在于每个解决方案中。

所以每个解决方案都包含 $z$. 。我们知道

$(-2K(n+1) - n) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}} + 1) + \sum { ext{引体向上}} = 0$,

我们可以重新排列这些术语：

$-2K(n+1) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}}) - (n + \sum_{i'= 1}^{m'} 1 + \sum { ext{上拉}}) = 0$

$-2K(n+1) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}}) - (n + m' + \sum { ext{引体向上}}) = 0$

$2(n+1)(-K + \sum_{i'=1}^{m'} x_{j'_{i'}}) - (n + m' + \sum { ext{引体向上}}) = 0$.

由于总和为 0，因此取模时必须保持为 0 $2(n+1)$, ，这意味着我们可以丢弃所有包含多个的项 $2(n+1)$ 得到新的方程

$-(n + m' + \sum { ext{上拉}}) = 0$.

这可以直接代入前面的方程得到

$2(n+1)(-K + \sum_{i'=1}^{m'} x_{j'_{i'}}) = 0$.

最后将两边除以 $2(n+1)$ 树叶

$-K + \sum_{i'=1}^{m'} x_{j'_{i'}} = 0$,

这产生了原始一般问题实例的解决方案。