一组的总和(逻辑) [英] Total sum from a set (logic)

问题描述

我有一个 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:

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

提前致谢！

推荐答案

这是子集求和问题m，这是一个已知的 NP-Complete 问题，因此没有已知的有效(多项式)解.

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) 开始迭代(假设该值为真)-您执行以下操作(在矩阵已填充之后):

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-arr[i-1],i-1) == true AND D(x,i-1) == true 随机选择要采取的行动.

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 代码(如果你不知道 python 把它看成伪代码，很容易理解)

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

附言

以上给你随机选择，但不是排列的均匀分布.
要实现均匀分布，您需要计算可能的选择数量以构建每个数字.
公式为:

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-arr[i],i-1)/D 添加元素 i(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)

这篇关于一组的总和(逻辑)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！