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

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

2011-06-13T17:44:03Z

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

WikiSysop: 1 версия

2008-08-04T09:55:52Z

1 версия

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

2006-07-25T03:48:31Z

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

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

Методы динамического программирования дают возможность построить для [[задача о рюкзаке|задачи о рюкзаке]] псевдополиномиальные алгоритмы, использующие при своей работе массивы, превышающие (возможно экспоненциально) длину входных данных.

Например, следующий алгоритм использует хранение наилучших частичных решений-наборов, в хэш-таблице, т. е. для каждого веса, если существует набор с таким весом, храниться максимальная стоимость.
Стартовав с пустого множества частичных наборов, и добавляя по одному, предметы, в каждый момент мы имеем не более ''B'' «лучших» частичных наборов, помещающихся в рюкзак.
В конце остается только выбрать самый дорогой из них.
Таким образом, хотя сложность этого алгоритма — ''O(nB)'' является экспоненциальной от длины входа, при ограниченных размерах рюкзака ''B'', алгоритм может быть полезен и эффективен.
Также можно организовать отбор ''наиболее легких'' решений, для каждой возможной стоимости набора,
как это сделано в [[Задача о рюкзаке:PTAS]].

Реализация алгоритма на [[Python]] и пример его выполнения:
<code-python>
def knapsack_dylp(A,B,C):
print "A=",A,"B=",B,"C=",C
T={0:0} #Хэш: самая большая стоимость набора для веса - {вес:стоимость}
Solution={0:[]}
#Цикл по всем предметам $\frac{c_i}{a_i}$
for i in range(0,len(A)):
print C[i],"/",A[i],":",
T_old=dict(T) #Копируем $T_{k-1}$ в $T_{old}$
print T
#Цикл по всем полученным частичным суммам
for x in T_old:
if (x+A[i])<=B:
if (not T.has_key(x+A[i])) or (T[x+A[i]]<T_old[x]+C[i]):
T[x+A[i]]=T_old[x]+C[i]
Solution[x+A[i]]=Solution[x]+[i]
print " -->",T

ResultCost = max(T.values())
Result = Solution[argmax(T)]
print Result,":",ResultCost
return (Result,ResultCost)
</code-python>

A= [6, 3, 2, 5, 5, 1] B= 10 C= [3, 4, 5, 6, 7, 8]
3 / 6 : {0: 0}
--> {0: 0, 6: 3}
4 / 3 : {0: 0, 6: 3}
--> {0: 0, 9: 7, 3: 4, 6: 3}
5 / 2 : {0: 0, 9: 7, 3: 4, 6: 3}
--> {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 8: 8, 9: 7}
6 / 5 : {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 8: 8, 9: 7}
--> {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 7: 11, 8: 10, 9: 7, 10: 15}
7 / 5 : {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 7: 11, 8: 10, 9: 7, 10: 15}
--> {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 7: 12, 8: 11, 9: 7, 10: 16}
8 / 1 : {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 7: 12, 8: 11, 9: 7, 10: 16}
--> {0: 0, 1: 8, 2: 5, 3: 13, 4: 12, 5: 9, 6: 17, 7: 12, 8: 20, 9: 19, 10: 16}
[2, 4, 5] : 20

[[Category:Алгоритмы]]
{{replicate-from-custiswiki-to-lib}}

Mazine: Fixed TeX formulae

2006-07-24T11:17:15Z

Fixed TeX formulae

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

2005-08-24T00:44:45Z

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

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

2005-08-23T15:18:23Z

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

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

← Предыдущая	Версия 00:44, 24 августа 2005
(не показана 1 промежуточная версия 1 участника)
(нет различий)

@@ Строка 1: / Строка 1: @@
-Методы динамического программирования дают возможность построить для [[задача о рюкзаке|задачи о рюкзаке]] псевдополиномиальные алгоритмы, использующие при своей работе массивы, превышающие (возможно экспоненциально) длину входных данных.
+#REDIRECT [[discopal:{{PAGENAME}}]]
-−
-Например, следующий алгоритм использует хранение наилучших частичных решений-наборов, в хэш-таблице, т. е. для каждого веса, если существует набор с таким весом, храниться максимальная стоимость.
-Стартовав с пустого множества частичных наборов, и добавляя по одному, предметы, в каждый момент мы имеем не более ''B'' «лучших» частичных наборов, помещающихся в рюкзак.
-В конце остается только выбрать самый дорогой из них.
-Таким образом, хотя сложность этого алгоритма — ''O(nB)'' является экспоненциальной от длины входа, при ограниченных размерах рюкзака ''B'', алгоритм может быть полезен и эффективен.
-Также можно организовать отбор ''наиболее легких'' решений, для каждой возможной стоимости набора,
-как это сделано в [[Задача о рюкзаке:PTAS]].
-−
-Реализация алгоритма на [[Python]] и пример его выполнения:
-<code-python>
- def knapsack_dylp(A,B,C):
-    print "A=",A,"B=",B,"C=",C
-    T={0:0} #Хэш: самая большая стоимость набора для веса - {вес:стоимость}
-    Solution={0:[]}
-    #Цикл по всем предметам $\frac{c_i}{a_i}$
-    for i in range(0,len(A)):
-        print C[i],"/",A[i],":",
-        T_old=dict(T)  #Копируем $T_{k-1}$ в $T_{old}$
-        print T
-        #Цикл по всем полученным частичным суммам
-        for x in T_old:
-            if (x+A[i])<=B:
-                if (not T.has_key(x+A[i])) or (T[x+A[i]]<T_old[x]+C[i]):
-                    T[x+A[i]]=T_old[x]+C[i]
-                    Solution[x+A[i]]=Solution[x]+[i]
-        print "    -->",T
-−
-    ResultCost = max(T.values())
-    Result = Solution[argmax(T)]
-    print Result,":",ResultCost
-    return (Result,ResultCost)
-</code-python>
-−
- A= [6, 3, 2, 5, 5, 1] B= 10 C= [3, 4, 5, 6, 7, 8]
-/ 6 : {0: 0}
-     --> {0: 0, 6: 3}
-/ 3 : {0: 0, 6: 3}
-     --> {0: 0, 9: 7, 3: 4, 6: 3}
-/ 2 : {0: 0, 9: 7, 3: 4, 6: 3}
-     --> {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 8: 8, 9: 7}
-/ 5 : {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 8: 8, 9: 7}
-     --> {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 7: 11, 8: 10, 9: 7, 10: 15}
-/ 5 : {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 7: 11, 8: 10, 9: 7, 10: 15}
-     --> {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 7: 12, 8: 11, 9: 7, 10: 16}
-/ 1 : {0: 0, 2: 5, 3: 4, 5: 9, 6: 3, 7: 12, 8: 11, 9: 7, 10: 16}
-     --> {0: 0, 1: 8, 2: 5, 3: 13, 4: 12, 5: 9, 6: 17, 7: 12, 8: 20, 9: 19, 10: 16}
- [2, 4, 5] : 20
-−
-−
-[[Category:Алгоритмы]]
-{{replicate-from-custiswiki-to-lib}}