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

I have a logic problem for an iOS app but I don't want to solve it using brute-force.

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

I have a set of integers, the values are not unique:

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

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

How can I get a subset from it with these 3 conditions:

在此先感谢！

推荐答案

这是子集和proble 米，它是一种公知的NP完全问题，因此没有已知有效（多项式）溶液到它。

This is the subset sum problem, it is a known NP-Complete problem, and thus there is no known efficient (polynomial) solution to it.

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

However, if you are dealing with only relatively low integers - there is a pseudo polynomial time solution using Dynamic Programming.

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

The idea is to build a matrix bottom-up that follows the next recursive formulas:

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)

我们的想法是模仿穷举搜索 - 在每个点你猜测如果元素被选择或不

The idea is to mimic an exhaustive search - at each point you "guess" if the element is chosen or not.

要得到实际的一部分，你需要追溯你的矩阵。您遍历从 D（SUM，N），（假设值是true） - 您执行以下（在矩阵已经填补了）：

To get the actual subset, you need to trace back your matrix. You iterate from D(SUM,n), (assuming the value is true) - you do the following (after the matrix is already filled up):

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-改编[I-1]，I-1）==真和 D（X，I-1）==真随机选择其中行动方针采取。

To get a random subset at each time, if both D(x-arr[i-1],i-1) == true AND D(x,i-1) == true choose randomly which course of action to take.

Python的code（如果你不知道蟒蛇读为假code，也很容易跟随）。

Python Code (If you don't know python read it as pseudo-code, it is very easy to follow).

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。

上面给你随意选择，而与排列的均匀分布。 要达到均匀分布，则需要为计数可能选择的数目打造每个号码。 维基，公式为：

The above give you random choice, but NOT with uniform distribution of the permutations. To achieve uniform distribution, you need to count the number of possible choices to build each number. The formulas will be:

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-改编[ I]，I-1）/ D（X，I）

And when generating the permutation, you do the same logic, but you decide to add the element i in probability D(x-arr[i],i-1) / D(x,i)