目标总和非零的子集总和变量 [英] Subset sum variant with a non-zero target sum

问题描述

我有一个整数数组，需要在子集和算法上应用变体它，除了寻找一组总和为 n 的整数而不是寻找一个总和为0的整数。对于如何使标准子集和算法之一适应这种变体，我还不清楚，希望对这个问题有任何见识。

I have an array of integers and need to apply a variant of the subset sum algorithm on it, except that instead of finding a set of integers whose sum is 0 I am trying to find a set of integers whose sum is n. I am unclear as to how to adapt one of the standard subset sum algorithms to this variant and was hoping for any insight into the problem.

推荐答案

这是子集总和问题，即 NP-完全（没有已知的有效解决NP-完全问题的方法），但是如果您的数字是相对较小的整数-是重复出现之后的有效伪多项式解：

This is subset sum problem, which is NP-Complete (there is no known efficient solution to NP-Complete problems), but if your numbers are relatively small integers - there is an efficient pseudo polynomial solution to it that follows the recurrence:

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)

以后，您需要退后一步，请参见在生成的矩阵上决定减少（采用元素）的位置，而决定不对减少（不采用元素）的位置。

Later, you need to step back on your choices, see where you decided to "reduce" (take the element), and where you decided not to "reduce" (not take the element), on the generated matrix.

< href = https：// stackoverflow.com/q/7489398/572670>此线程和此线程讨论如何获取元素对于类似的问题。

This thread and this thread discuss how to get the elements for similar problems.

这是完成此操作的python代码（来自我链接到的线程）。

如果您不熟悉python，请将其作为伪代码阅读，这很容易理解python！。

Here is a python code (taken from the thread I linked to) that does the trick.
If you are not familiar with python - read it as pseudo code, it's pretty easy to understand 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

这篇关于目标总和非零的子集总和变量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！