Алгоритм рюкзака :PTAS
Динамическое программирования для рюкзака, с отбором «наиболее легких» частичных решений.
def knapsack_dylp_lightest(A,B,C):
T={0:0} #Хэш: самый малый вес для стоимости - {стоимость:минимальный вес}
Solution={0:[]}
#Цикл по всем предметам $\frac{c_i}{a_i}$
for i in range(0,len(A)):
T_old=dict(T) #Копируем $T_{k-1}$ в $T_{old}$
for x in T_old:
if (T_old[x]+A[i])<=B:
if (not T.has_key(x+C[i])) or (T_old[x]+A[i]<T_old[x+C[i]]):
T[x+C[i]]=T_old[x]+A[i]
Solution[x+C[i]]=Solution[x]+[i]
ResultCost = max(T.keys())
Result = Solution[ResultCost]
return Result
PTAS для рюкзака. Общая схема.
def knapsack_ptas_generic(A,B,C,epsilon, f_lower_bound):
print "A=",A
print "B=",B
print "C=",C
print "epsilon=",epsilon
#Вычисляем нижнюю оценку стоимости и параметр округления $scale$
F_lb=f_lower_bound(A,B,C)
print "F_lb=",F_lb
scale=floor(epsilon*F_lb/len©/(1+epsilon))
print "scale=",scale
#Округляем коэффициенты
C_=[]
for i in range(0,len(A)):
C_.insert(i, int(floor(C[i] / scale)))
print "C_=",C_
ApproxResult=knapsack_dylp_lightest(A,B,C_)
ApproxCost=0
for i in ApproxResult:
ApproxCost=ApproxCost+C[i]
return (ApproxResult,ApproxCost)
def knapsack_lower_bound_trivial(A,B,C):
#Простая оценка нижней границы стоимости решения.
return max©
def knapsack_lower_bound_greedy(A,B,C):
#Оценка нижней границы через жадный алгоритм.
return knapsack_greedy(A,B,C)
PTAS для рюкзака, сложности $O(\frac{n³}{\varepsilon})$
def knapsack_ptas_trivial(A,B,C,epsilon):
return knapsack_ptas_generic(A,B,C,epsilon,knapsack_lower_bound_trivial)
- PTAS для рюкзака, сложности $O(\frac{n²}{\varepsilon})$
def knapsack_ptas_nontrivial(A,B,C,epsilon):
return knapsack_ptas_generic(A,B,C,epsilon,knapsack_lower_bound_greedy)
knapsack_ptas_trivial:
A= [16, 900, 440, 250, 667, 43, 333, 857, 474]
B= 1000
C= [134, 1354, 567, 789, 987, 56, 345, 4567, 5555]
epsilon= 0.1
F_lb= 5555
scale= 56.0
C_= [2, 24, 10, 14, 17, 1, 6, 81, 99]
Cost= 6534
knapsack_ptas_nontrivial:
A= [16, 900, 440, 250, 667, 43, 333, 857, 474]
B= 1000
C= [134, 1354, 567, 789, 987, 56, 345, 4567, 5555]
epsilon= 0.1
F_lb= 6534
scale= 66.0
C_= [2, 20, 8, 11, 14, 0, 5, 69, 84]
Cost= 6478
knapsack_ptas_nontrivial:
A= [16, 900, 440, 250, 667, 43, 333, 857, 474]
B= 1000
C= [134, 1354, 567, 789, 987, 56, 345, 4567, 5555]
epsilon= 0.08
F_lb= 6534
scale= 53.0
C_= [2, 25, 10, 14, 18, 1, 6, 86, 104]
Cost= 6534
