0

问题陈述如下：给定N。我们需要找到x1, x2, ..,xp使得N = x1 + x2 + .. + xp, p 必须是最小值（表示总和中的项数），并且我们还必须能够从 ( x1,x2,x3..xp)。集合中的数字也可能重复。

例如，如果 N=7。

7 = 1+2+4 和6= (2,4), 5= (4,1), 4 = (4),3=(1,2)等等。

示例 2： 8 = 1+2+4+1

示例 3：（无效）8 = 1+2+5 但我们无法从 (1,2,5) 的子集中得到 4。所以 (1,2,5) 不是有效组合

我的方法是，如果“N-1”可以写成 p 项的总和，那么“N”要么有 p 项，要么有 p+1 项。但是这种方法需要检查所有可能的组合，这些组合总和为“N-1”并具有“p”项。谁能有比这更好的解决方案？

解决方案：

Step1：假设我们在我们的集合中有“K”个条目作为我们的答案。因此，我们可以从这些数字中获得 2^K 个不同数量的总和，因为每个条目要么出现在总和中，要么不出现在总和中。而且如果数字是“N”，我们需要计算“1”到“N”的总和。因此

(2^K -1) = N

K=log(N+1)

Step2：

在 step1 之后，我们知道我们的答案必须包含“K”个条目，但这些条目实际是什么？假设我们的条目是 (a1,a2,a3...ak)。所以数字 P 可以写成 P = a1*b1 + a2*b2 + a3*b3....+ ak*bk。其中所有 b[i] = 0 或 1。在这里，我们可以将 P 视为二进制数 (b1 b2 b3 bk) 的十进制表示，因此我们可以取 a[i] = 2^(i-1)。

4

2 回答 2

5

您应该取所有数字 1,2,4 ....2^k, N-(1+...+2^k)。（最后一个仅当它不等于 0 时）

证明

  1. 首先，如果我们只得到k数字，我们可以得到2^k - 1除 0 之外的最大不同和。所以如果N>=2^k，我们至少需要k + 1数字。所以你可以看到，如果我们的数字组正确，它的大小是最小值（或最小值之一）

  2. 很容易看出，我们可以得到从 0 到2^(k+1) - 1使用第一个数字的任何数字。如果我们需要更多怎么办？我们只得到最后一个数字，因为它小于2^(k + 1)。并使用第一个元素获得差异

于 2013-07-13T02:28:15.367 回答
0

我没有用完这方面的数字，但是您应该对您列出了 2 的前三个幂这一事实非常感兴趣。

如果我正在寻找更好的解决方案，那就是我要开始的地方。

于 2013-07-13T02:10:38.213 回答