|
|
| Строка 1: |
Строка 1: |
| − | Жадный алгоритм для [[задача о рюкзаке|задачи о рюкзаке]]
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | состоит в следующем (считаем, что все предметы помещаются в рюкзак):
| + | |
| − | | + | |
| − | * Выбрать максимально дорогой предмет, стоимости ''C<sub>max</sub>'' .
| + | |
| − | * Упорядочить предметы по «удельной стоимости» (стоимости деленной на вес), и набивать рюкзак наиболее «удельно дорогими» предметами, пока они влезают. Пусть стоимость этого решения ''C<sub>greedy</sub>''
| + | |
| − | * В зависимости от того, что больше, ''C<sub>max</sub>'' или ''C<sub>greedy</sub>'', выбрать первое или второе решение.
| + | |
| − | | + | |
| − | Этот алгоритм имеет сложность ''O(n log(n))'', и гарантирует нахождение решения, не хуже чем в два раза от оптимального.
| + | |
| − | | + | |
| − | Реализация на языке [[Python]] и примеры выполнения алгоритма приведены ниже:
| + | |
| − | | + | |
| − | <code-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
| + | |
| − | </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
| + | |
| − | | + | |
| − | | + | |
| − | | + | |
| − | [[Category:Алгоритмы]]
| + | |
| − | {{replicate-from-custiswiki-to-lib}} | + | |
