Традиция

Текст:Задача о рюкзаке: жадный алгоритм

(перенаправлено с «Задача о рюкзаке:жадный алгоритм»)

Жадный алгоритм для задачи о рюкзаке состоит в следующем (считаем, что все предметы помещаются в рюкзак):

  • Выбрать максимально дорогой предмет, стоимости Cmax .
  • Упорядочить предметы по «удельной стоимости» (стоимости деленной на вес), и набивать рюкзак наиболее «удельно дорогими» предметами, пока они влезают. Пусть стоимость этого решения Cgreedy
  • В зависимости от того, что больше, Cmax или Cgreedy, выбрать первое или второе решение.

Этот алгоритм имеет сложность O(n log(n)), и гарантирует нахождение решения, не хуже чем в два раза от оптимального.

Реализация на языке Python и примеры выполнения алгоритма приведены ниже:

<code-python>

  1. Жадный алгоритм для задачи о рюкзаке.

def knapsack_greedy(A,B,C): 

   print "A=",A,"B=",B,"C=",C
   T={}
   for i in range(0,len(A)):
       T[float(A[i])/float(C[i])]=i

   #Сортируем ключи - "удельную привлекательность" - по убыванию
   K=T.keys(); K.sort() 
   print "K=",K

   # Набиваем рюкзак до наполнения, предметами в порядке их полезности.
   C_greedy=0; W_greedy=0;
   for i in K:
       if W_greedy+A[T[i]]<=B:
         W_greedy=W_greedy+A[T[i]]
         print "Get item (",C[T[i]],"/",A[T[i]],")"  
         C_greedy=C_greedy+C[T[i]]
   
   C_max=max(C)
   print "C_greedy=",C_greedy,"C_max=",C_max
   
   C_result=max(C_greedy,C_max)         
   print "Result=",C_result
   return C_result

</code-python> 

A= [6, 3, 2, 5, 5, 1] B= 10 C= [3, 4, 5, 6, 7, 8] 
K= [0.125, 0.40000000000000002, 0.7142857142857143, 0.75, 0.83333333333333337, 2.0]
Get item ( 8 / 1 )
Get item ( 5 / 2 )
Get item ( 7 / 5 )
C_greedy= 20 C_max= 8
Result= 20

A= [1, 100, 40, 20] B= 100 C= [10, 150, 50, 40]
K= [0.10000000000000001, 0.5, 0.66666666666666663, 0.80000000000000004]
Get item ( 10 / 1 )
Get item ( 40 / 20 )
Get item ( 50 / 40 )
C_greedy= 100 C_max= 150
Result= 150


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.

Источник — https://traditio.wiki/w/index.php?title=Текст:Задача_о_рюкзаке:_жадный_алгоритм&oldid=702532