子集合動態編程

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