子集和动态规划

Question

def subset(array, target):
    sol = [[False for x in range(target + 1)] for x in range(len(array) + 1)]
    for i in range(len(array)+1):
        sol[i][0] = True
    for i in range(1,(len(array)+1)):
        for j in range(1, target+1):
            if (j - array[i-1] >= 0):
                sol[i][j] = sol[i-1][j] | sol[i-1][j - array[i-1]]
            else:
                sol[i][j] = sol[i-1][j]
    printSub(sol, array, target)
    return sol[len(array)][target]

def printSub(sol, array, target):
    if(sol[len(array)][target]):
        print("Found!")
        i = len(array)
        j = target
        while(j!=0):
            if(sol[i-1][j] == True):
                i-=1
            else:
                print(array[i-1], end = " ")
                j = j - array[i-1]
    else:
        print("No combination found! ")

我有一个子集问题的工作代码，如果它发现一个子集等于所需的目标，它可以打印数字。

>

我想打印给定目标的所有可能的子集，我不知道要为此更改什么。

我如何让它对负数起作用？

Answer 1

**1） **将printsub的功能更改为1到len（array），并使用if（sol[i][target]）而不是（sol[len（array）][target]）。

**2） **双回路后-

for i in range(1,(len(array)+1)):
    for j in range(1, target+1):

添加一个条件，检查数组[i-1]是否为负，如果为正，则无需更改任何其他内容

 if (j - array[i-1] >= 0):
            sol[i][j] = sol[i-1][j] | sol[i-1][j - array[i-1]]

**3） **这里有相同问题的链接-减少0-1背包问题的时间复杂性