用于获得具有最小项数的和的算法

Question

问题陈述如下:给定N.我们需要找到x1,x2,..,xp这样N = x1 + x2 + .. + xp,p必须是最小的(指在和项数),我们还必须能够从子集的总和从1得到的所有号码(N-1)( 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)

步骤2:

在步骤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).并使用第一个元素获得差异