Освежая динамическое программирование (DP), когда я столкнулся с этой проблемой. Мне удалось использовать DP, чтобы определить, сколько решений есть в задаче о сумме подмножеств.
def SetSum(num_set, num_sum):
#Initialize DP matrix with base cases set to 1
matrix = [[0 for i in range(0, num_sum+1)] for j in range(0, len(num_set)+1)]
for i in range(len(num_set)+1): matrix[i][0] = 1
for i in range(1, len(num_set)+1): #Iterate through set elements
for j in range(1, num_sum+1): #Iterate through sum
if num_set[i-1] > j: #When current element is greater than sum take the previous solution
matrix[i][j] = matrix[i-1][j]
else:
matrix[i][j] = matrix[i-1][j] + matrix[i-1][j-num_set[i-1]]
#Retrieve elements of subsets
subsets = SubSets(matrix, num_set, num_sum)
return matrix[len(num_set)][num_sum]
На основе Subset sum — Recover Solution я использовал следующий метод для извлечения подмножеств, поскольку набор всегда будет отсортировано:
def SubSets(matrix, num_set, num):
#Initialize variables
height = len(matrix)
width = num
subset_list = []
s = matrix[0][num-1] #Keeps track of number until a change occurs
for i in range(1, height):
current = matrix[i][width]
if current > s:
s = current #keeps track of changing value
cnt = i -1 #backwards counter, -1 to exclude current value already appended to list
templist = [] #to store current subset
templist.append(num_set[i-1]) #Adds current element to subset
total = num - num_set[i-1] #Initial total will be sum - max element
while cnt > 0: #Loop backwards to find remaining elements
if total >= num_set[cnt-1]: #Takes current element if it is less than total
templist.append(num_set[cnt-1])
total = total - num_set[cnt-1]
cnt = cnt - 1
templist.sort()
subset_list.append(templist) #Add subset to solution set
return subset_list
Однако, поскольку это жадный подход, он работает только тогда, когда максимальный элемент каждого подмножества различен. Если два подмножества имеют одинаковый максимальный элемент, он возвращает только тот, у которого больше значение. Итак, для элементов [1, 2, 3, 4, 5] с суммой 10 он возвращает только
[1, 2, 3, 4] , [1, 4, 5]
Когда он должен вернуться
[1, 2, 3, 4] , [2, 3, 5] , [1, 4, 5]
Я мог бы добавить еще один цикл внутри цикла while, чтобы исключить каждый элемент, но это увеличило бы сложность до O (строки ^ 3), что потенциально может быть больше, чем фактический DP, O (строки * столбцы). Есть ли другой способ получить подмножества без увеличения сложности? Или отслеживать подмножества во время подхода DP? Я создал еще один метод, который может получить все уникальные элементы в подмножествах решений за O(строки):
def RecoverSet(matrix, num_set):
height = len(matrix) - 1
width = len(matrix[0]) - 1
subsets = []
while height > 0:
current = matrix[height][width]
top = matrix[height-1][width]
if current > top:
subsets.append(num_set[height-1])
if top == 0:
width = width - num_set[height-1]
height -= 1
return subsets
Что выведет [1, 2, 3, 4, 5]. Однако получение из него фактических подмножеств похоже на решение проблемы подмножества заново. Любые идеи/предложения о том, как хранить все подмножества решений (не печатать их)?
