%
Алгоритм Рюкзака

Меню сайта

Статистика
Рейтинг@Mail.ru Яндекс.Метрика

Алгоритм рюкзака :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)

  1. 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

 
 
 
 

Назад Домой Вперед

 

Друзья сайта
  • Группа AR в ВК.
  • Группа AR в FB.
  • Группа AR в OK.
  • Алгебра Логики.
  • Альтернатива Групп.

  • Алгоритм Рюкзака © 2017 created AD.