|
Персональные инструменты |
![]() |
||
|
![]() |
![]() Задача о рюкзаке:динамическое программированиеМатериал из CustisWikiВерсия от 06:48, 25 июля 2006; BenderBot (обсуждение | вклад) (реплицировано из внутренней CustisWiki) Методы динамического программирования дают возможность построить для задачи о рюкзаке псевдополиномиальные алгоритмы, использующие при своей работе массивы, превышающие (возможно экспоненциально) длину входных данных. Например, следующий алгоритм использует хранение наилучших частичных решений-наборов, в хэш-таблице, т. е. для каждого веса, если существует набор с таким весом, храниться максимальная стоимость. Стартовав с пустого множества частичных наборов, и добавляя по одному, предметы, в каждый момент мы имеем не более B «лучших» частичных наборов, помещающихся в рюкзак. В конце остается только выбрать самый дорогой из них. Таким образом, хотя сложность этого алгоритма — O(nB) является экспоненциальной от длины входа, при ограниченных размерах рюкзака B, алгоритм может быть полезен и эффективен. Также можно организовать отбор наиболее легких решений, для каждой возможной стоимости набора, как это сделано в Задача о рюкзаке:PTAS. Реализация алгоритма на 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) 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
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «Задача о рюкзаке:динамическое программирование» |
![]() |
![]() |
![]() |