获得最少项数总和的算法

Question

问题陈述如下:给定 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”项。除了这个还有其他更好的解决方案吗？

解决方法:

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

(2^K -1) = N

K=log(N+1)

第二步:

在第 1 步之后，我们知道我们的答案必须包含“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)。

Answer 1

你应该取所有数字 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)。并使用第一个元素获得差异