Экономико-математические методы и модели. Основы динамического программирования. Задача о рюкзаке
Учебные вопросы Основы динамического программирования: Решение задачи «О рюкзаке» методом динамического программирования ЭММ лекция 10 23.04.2020 Имеется рюкзак с заданной вместимостью (под вместимостью понимается максимально возможная масса), и имеются предметы (n штук), причем каждый предмет характеризуется массой w и ценностью P.
w = {w1, w2, …, wn}
p={p1, p2, …, pn} Требуется собрать рюкзак с максимальной ценностью и минимальным возможным весом, не превышающим Wmax.
1 способ: перебор (простой)
2 способ: метод ветвей и границ, который заключается в умном переборе. Могут быть случаи, когда перебираются все возможные варианты.
3 способ: использование «жадного» алгоритма (берется каждый текущий момент («лучший» элемент), ориентированный на их относительной точности). Решение будет получено достаточно быстро, но не факт, что оно будет оптимальным.