从一组（逻辑）

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

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

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

我如何从这三个条件中获得一个子集：

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

提前致谢！

Answer 1

这是子集和问题 ，这是一个已知的NP完全问题，因此没有已知的有效（多项式）解决scheme。

但是 ，如果您只处理相对较低的整数，则使用dynamic规划有一个伪多项式时间解决scheme。

这个想法是build立一个matrix自下而上的下一个recursion公式：

 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) 

这个想法是模仿一个彻底的search – 在每个点你猜“如果元素是select或不。

为了得到实际的子集，你需要追溯你的matrix。 你从D(SUM,n)迭代（假设值是真的） – 你做了以下的事情（在matrix已经被填满之后）：

 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 AND D(x,i-1) == true ，那么每次都要随机select一个子集。

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(xr) #modify i and x accordingly x = r i = i-1 print sol 

PS

以上给出了随机select，但不是均匀分布的排列。
要实现统一的分配，您需要计算可能的select数量来构build每个数字。
公式将是：

 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) 

当产生置换时，你做同样的逻辑，但是你决定把元素ijoin概率D(x-arr[i],i-1) / D(x,i)