|
Персональные инструменты |
![]() |
||
|
![]() |
![]() Задача о рюкзаке:жадный алгоритм — различия между версиямиМатериал из CustisWiki
Версия 12:55, 4 августа 2008Жадный алгоритм для задачи о рюкзаке состоит в следующем (считаем, что все предметы помещаются в рюкзак):
Этот алгоритм имеет сложность O(n log(n)), и гарантирует нахождение решения, не хуже чем в два раза от оптимального. Реализация на языке Python и примеры выполнения алгоритма приведены ниже: # Жадный алгоритм для задачи о рюкзаке. 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 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
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «Задача о рюкзаке:жадный алгоритм» |
![]() |
||||||
![]() |
![]() |