找到整数列表的校验和

我需要的ň正整数大号列表，具有以下特点：找到整数列表的校验和

对每个可能的子集小号的大号，如果我综上所述小号的所有项目，这个总和不大号
对于每个可能子集的小号大号，如果我总结小号的所有项目，这个总和是唯一的（每个子集可以通过他的总和确定的）

工作实施例1：

n = 4 
L = [1, 5, 7, 9] 

check: 
1+5 = 6 ok 
5+7 = 12 ok 
7+9 = 16 ok 
9+1 = 10 ok 
1+7 = 8 ok 
5+9 = 14 ok 

1+5+7 = 13 ok 
5+7+9 = 21 ok 
1+5+9 = 15 ok 
1+7+9 = 17 ok 

1+5+7+9 = 22 ok 

All sums are unique -> L is OK for n = 4

来源

2016-12-22 DPColombotto

你为什么不试试质数？ –

@WasiAhmad只使用素数并不保证它。例如，5 + 13 = 7 + 11。 – njlarsson

“对于L的每个可能的子集S，如果我将S的所有项相加，则该总和不在L中”如果该子集仅包含一个元素，该怎么办？从你的例子看来，你只考虑具有2个或更多元素的子集？请确认。 –

作为容易构造序列，我建议使用电源系列，例如

1, 2, 4, 8, ..., 2**k, ... 
1, 3, 9, 27, ..., 3**k, ... 
1, 4, 16, 64, ..., 4**k, ... 
... 
1, n, n**2, n**3,..., n**k, ... where n >= 2

采取的，例如，2：的2力量也不是其他2功率的总和;通过转换sum成二进制表示法给出一个sum（数量），你可以很容易找到的子集：

23 = 10111 (binary) = 2**0 + 2**1 + 2**2 + 2**4 = 1 + 2 + 4 + 16

在一般情况下，一个简单的贪心算法会做：给定一个sum减去最大项小于或等于到sum;继续减去零：

n = 3 
sum = 273 

273 - 243 (3**5) = 30 
    30 - 27 (3**3) = 3 
    3 - 3 (3**1) = 0 

273 = 3**5 + 3**3 + 3**1 = 243 + 27 + 3

来源

2016-12-22 10:02:05

很好的答案..！ –

找到整数列表的校验和

回答

相关问题