子集合动态编程

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! ") 

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

1. 我想打印给定目标的所有可能的子集，我不明白要改变什么。

2. 如何使它适用于负数？

3. 时间复杂度是O（len（array）* target），我相信这个空间是相同的。有什么方法可以改善吗？

Answer 1

** 1）**通过1更改该printsub函数是循环的i到len(array)并使用if(sol[i][target])代替(sol[len(array)][target])。

** 2）**双loops-后

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

补充说，检查的条件，如果array[i-1]为负或不if它是积极的，不需要改变什么else通过target+2-j在

更换 j

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

** 3）**这里的链接到同一ques- Reducing time complexity of 0-1 Knapsack problem