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[0]/float(x[1]),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[1] for numb in x])(n))
            if weight <= limit:
                cost = reduce(operator.add,(lambda x: [numb[0] 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[1] for x in current_objects]),limit),'objects':current_objects}
    
print PTAS_KP(objects,limit = 16, E = 0.001)
Google