Abaixo eu apresento 4 soluções diferentes usando backtracking. Todas elas se baseiam no seguinte argumento:
Existe um subconjunto que soma \(T\) se, e somente se, uma das afirmativas é verdadeira:
Existe um subconjunto de \(X\) que inclui \(x\) que a soma é \(T\)
Existe um subconjunto de \(X\) que exclui \(x\) que a soma é \(T\)
De fato, as duas primeiras soluções são baseadas nos pseudo-códigos na Lecture 3 do E-book Algorithms de Jeff Erickson. As últimas soluções usam explicitamente a representação usando árvore binária usual para resolver problemas com essas características.
1) Checa se existe um subconjunto
import numpy as np
def subset_sum_check(theSet,target):
n=len(theSet)
if (target==0):
print "I found a solution"
return True
elif(target<0 or n==0):
return False
else:
return (subset_sum_check(theSet[0:n-1],target)or(subset_sum_check(theSet[0:n-1],target-theSet[n-1])))
if __name__ == '__main__':
theSet=np.array([8,6,7,5,3,10,9])
target=15
solution=[]
print subset_sum_check(theSet,target)
2) Apresenta um subconjunto
import warnings
import numpy as np
def subset_sum(theSet,target):
n=len(theSet)
if(target==0):
return np.empty([0]) #emptySet
if(target<0 or n==0):
return None
theAuxSet=subset_sum(theSet[0:n-1],target)
if (theAuxSet is not None):
return theAuxSet
theAuxSet=subset_sum(theSet[0:n-1],target-theSet[n-1])
if(theAuxSet is not None):
return np.append(theAuxSet,theSet[n-1])
return None
if __name__ == '__main__':
theSet=np.array([8,6,7,5,3,10,9])
target=16
solution=[]
#print list(subset_sum(theSet,target))
print subset_sum(theSet,target)
3 ) Apresenta todos os subconjuntos
a) Usando uma fila:
import numpy as np
import Queue
class Node:
def __init__(self, level, possibleSolution):
self.level = level # The level within the tree (depth)
self.possibleSolution = possibleSolution # list of items our node contains
def subset_sum(theSet,target):
solution=[]
n=len(theSet)
queue = Queue.Queue()
root = Node(-1,[])
queue.put(root)
while not queue.empty():
u=queue.get()
if(u.level<n-1):
# With the extra element
v=Node(u.level+1,u.possibleSolution[:])
v.possibleSolution.append(theSet[v.level])
sumPossibleSolution=sum(v.possibleSolution)
if(sumPossibleSolution==target):
solution.append(v.possibleSolution)
if(sumPossibleSolution<target):
queue.put(v)
# Without the extra element
v=Node(u.level+1,u.possibleSolution[:])
queue.put(v)
return solution
if __name__ == '__main__':
theSet=np.array([8,6,7,5,3,10,9])
target=15
solution=[]
#print list(subset_sum(theSet,target))
print subset_sum(theSet,target)
b) Usando uma pilha
import numpy as np
class Node:
def __init__(self, level, possibleSolution):
self.level = level # The level within the tree (depth)
self.possibleSolution = possibleSolution # list of items our node contains
def printNode(self):
print(self.possibleSolution,self.level, ' ,',end=' ')
def subset_sum(theSet,target):
solution=[]
n=len(theSet)
root = Node(-1,[])
stack=[root]
iteration=0
while len(stack)!=0:
iteration=iteration+1
print('\n',iteration)
for i in range(len(stack)):
stack[i].printNode()
u=stack.pop()
if(u.level<n-1):
# Without the extra element
v=Node(u.level+1,u.possibleSolution[:])
stack.append(v)
# With the extra element
v=Node(u.level+1,u.possibleSolution[:])
v.possibleSolution.append(theSet[v.level])
sumPossibleSolution=sum(v.possibleSolution)
if(sumPossibleSolution==target):
solution.append(v.possibleSolution)
print('\n','solution',solution)
if(sumPossibleSolution<target):
stack.append(v)
return solution
if __name__ == '__main__':
theSet=np.array([8,6,7,5,3,10,9])
target=15
solution=[]
print('theSolution')
print ('\n',subset_sum(theSet,target))