|
|
| (не показаны 4 промежуточные версии 3 участников) |
| Строка 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]
| + | |
| − | 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}}
| + | |
