# Polynomial time approximation scheme algorithm for KP (PTAS-KP)

A PTAS is an algorithm which takes an instance of an optimization problem and a parameter ε > 0 and, in polynomial time, produces a solution that is within a factor 1 + ε of being optimal [wikipedia]. This is an implementation to find solutions to the Knapsack Problem.

``````import itertools, math, operator

"""
S = Set of objects formatted as [ (cost,weight,object),(cost,weight,object),(cost,weight,object)]
limit = The weight limit of the knapsack
E = The acceptable deviation from det optimal solution as decimal. 1 < E < 0 The
"""

objects = [
#(cost,weight,object)
(1,4,None),
(4,5,None),
(3,8,None),
(7,3,None),
(4,30,None),
(2,1,None),
(8,8,None),
(12,2,None),
]

def PTAS_KP(S, limit, E):
if not 1 > E > 0:
raise ValueError( "The percentage allowed error value must be between 1 and 0. The closer to 0, \
the better the approximation. A value of 0.03 means you are willing to accept a result with a \
deviation of 3\% from the optimal score." )

S = sorted( S,key = lambda x: x/float(x),reverse=True )

k = int(math.ceil(1/E))
current_score = None
current_objects = []

for i in range(1,k if k<=len(S) else len(S) ):
for n in set(itertools.combinations(S, i)):
weight = reduce(operator.add,(lambda x: [numb for numb in x])(n))
if weight <= limit:
cost = reduce(operator.add,(lambda x: [numb for numb in x])(n))
if cost > current_score:
current_score = cost
current_objects = n

return {'cost':current_score,'weight to solution':'%d/%d' % (reduce(operator.add,[x for x in current_objects]),limit),'objects':current_objects}

print PTAS_KP(objects,limit = 16, E = 0.001)``````