从一套（逻辑）

Question

总笔数我有一个iOS应用程序的逻辑问题，但我不想用蛮力解决它。

我有一个整数集，值不是唯一的：

[3,4,1,7,1,2,5,6,3,4........] 

我怎样才能得到一个子集，从它与这3个条件：

• 我只能选择一个定义的量值。
• 拾取元素的总和等于一个值。
• 选择必须是随机的，所以如果有多个解决方案的值，它不会总是返回相同的。

在此先感谢！

Answer 1

这是subset sum proble m，这是一个已知的NP完全问题，因此没有已知的有效（多项式）解决方案。

然而，如果你正在处理，只有相对较低的整数 - 有使用Dynamic Programming一个伪多项式时间的解决方案。

的想法是建立一个矩阵自下而上而随后的递推公式：

D(x,i) = false x<0 
D(0,i) = true 
D(x,0) = false x != 0 
D(x,i) = D(x,i-1) OR D(x-arr[i],i-1) 

的想法是模仿穷举搜索 - 在每个点上你“猜”如果选择的元素或不。

要获得实际的子集，您需要追溯您的矩阵。您可以从D(SUM,n)迭代，（假设值是true） - 您做以下（后矩阵已经填满）：

if D(x-arr[i-1],i-1) == true: 
    add arr[i] to the set 
    modify x <- x - arr[i-1] 
    modify i <- i-1 
else // that means D(x,i-1) must be true 
    just modify i <- i-1 

要每次随机获得一个子集，如果两个D(x-arr[i-1],i-1) == true和D(x,i-1) == true随机选择采取何种行动。

Python代码（如果你不知道python将它读为伪代码，那么很容易遵循）。

arr = [1,2,4,5] 
n = len(arr) 
SUM = 6 
#pre processing: 
D = [[True] * (n+1)] 
for x in range(1,SUM+1): 
    D.append([False]*(n+1)) 
#DP solution to populate D: 
for x in range(1,SUM+1): 
    for i in range(1,n+1): 
     D[x][i] = D[x][i-1] 
     if x >= arr[i-1]: 
      D[x][i] = D[x][i] or D[x-arr[i-1]][i-1] 
print D 

#get a random solution: 

if D[SUM][n] == False: 
    print 'no solution' 
else: 
    sol = [] 
    x = SUM 
    i = n 
    while x != 0: 
     possibleVals = [] 
     if D[x][i-1] == True: 
      possibleVals.append(x) 
     if x >= arr[i-1] and D[x-arr[i-1]][i-1] == True: 
      possibleVals.append(x-arr[i-1]) 
     #by here possibleVals contains 1/2 solutions, depending on how many choices we have. 
     #chose randomly one of them 
     from random import randint 
     r = possibleVals[randint(0,len(possibleVals)-1)] 
     #if decided to add element: 
     if r != x: 
      sol.append(x-r) 
     #modify i and x accordingly 
     x = r 
     i = i-1 
    print sol 

P.S.

上面给你随机选择，但不是用均匀分布的排列组合。
要实现均匀分布，您需要数构建每个数字的可能选项数量。
公式为：

D(x,i) = 0 x<0 
D(0,i) = 1 
D(x,0) = 0 x != 0 
D(x,i) = D(x,i-1) + D(x-arr[i],i-1) 

，并产生置换的时候，你做同样的逻辑，但你决定在概率D(x-arr[i],i-1)/D(x,i)