Проблемы с рюкзаком легко решаются динамическим программированием. Динамическое программирование выполняется за полиномиальное время; вот почему мы делаем это, верно?
Я читал, что это на самом деле NP-полная проблема, однако это означает, что решить проблему в полиномиальной задаче, вероятно, невозможно.
Где моя ошибка?
Ответы:
Проблема ранец являетсяNP-complete , когда числа приведены в качестве двоичных чисел. В этом случае динамическое программирование будет завершаться экспоненциально за много шагов (по размеру входа, то есть по количеству битов на входе) до завершения † .
С другой стороны, если числа на входе даны в унарном порядке, динамическое программирование будет работать за полиномиальное время (по размеру входа).
Такого рода проблемы, называется слабоNP-complete .
Этот вид алгоритма, то есть полином по наибольшему числу, являющемуся частью входных данных, но экспоненциальный по длине входных данных, называется псевдополиномиальным .
источник
m
(размер упаковки) иn
(количество предметов) совершенно неизвестно, верно? И «когда числа даны как двоичные числа» ... но не могли бы вы сказать это ни за что? В большинстве алгоритмов мы говорим о размере входных данных в базе 10. Зачем здесь говорить о двоичном коде? И независимо от того, кодируете ли вы в двоичном, восьмеричном, десятичном и т. Д. Числе,actual
количество итераций в цикле основного алгоритма напрямую зависит от обоихn
иW
.Основная путаница заключается в разнице между « размером » и « стоимостью ».
« Полиномиальное время » подразумевает полином по величине ввода.
« Псевдополиномиальное время » подразумевает полиномиальное значение входного значения. Можно показать (ниже), что это эквивалентно экспоненциальной величине входных данных.
источник
Однако существуют различные варианты (например, 0-1 рюкзак и другие ), которые могут иметь или не иметь решения за полиномиальное время или хорошие приближения. Но это не то же самое, что общая проблема ранца. Кроме того, могут существовать эффективные алгоритмы, которые работают для конкретных (семейств) экземпляров , но эти алгоритмы потребуют больше времени в других экземплярах.
источник