集合的总和（逻辑）

Question

我有一个 iOS 应用程序的逻辑问题，但我不想使用暴力解决它。

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

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

如何在这 3 个条件下从中获取子集：

我只能选择定义数量的值。
所选元素的总和等于一个值。
选择必须是随机的，因此如果值有多个解，它不会总是return相同。

提前致谢！

Answer 1

这是 subset sum problem，这是一个已知的 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)

这个想法是模仿穷举搜索 - 在每个点你 "guess" 是否选择了元素。

要获得实际的子集，您需要追溯您的矩阵。您从 D(SUM,n) 开始迭代（假设该值为真）- 您执行以下操作（在矩阵已经填满之后）：

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)

的概率添加元素 i

集合的总和（逻辑）

Total sum from a set (logic)

algorithm

optimization

logic

brute-force

ios