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

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:44:21Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

WikiSysop: 1 версия

2008-08-04T09:55:52Z

1 версия

BenderBot: реплицировано из внутренней CustisWiki

2005-08-24T00:44:47Z

реплицировано из внутренней CustisWiki

Новая страница

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

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

Этот алгоритм имеет сложность ''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}}

StasFomin: начал первую версию из лекций.

2005-08-23T14:25:51Z

начал первую версию из лекций.

← Предыдущая	Версия 09:55, 4 августа 2008
(не показана 1 промежуточная версия 1 участника)
(нет различий)

@@ Строка 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}}

← Предыдущая	Версия 14:25, 23 августа 2005
(нет различий)