Это все еще динамическое программирование.Единственное отличие состоит в том, что алгоритм динамического программирования все еще не полиномиален в n, а в n и W.Для этих типов проблем необходимо различать значения, которые возникают естественным образом из-за ввода, и значения, которые part ввода.
Ваш ввод состоит из n различных элементов и число W;W явно, не подразумевается размером ввода.Поскольку мы используем некоторое эффективное кодирование (т. Е. Двоичное) для обеспечения W, размер W равен экспоненциальному в кодировке W.То есть вход содержит O (lg W) битов, представляющих W, но таблица, которую мы строим, имеет W строк (или столбцов, углубляющихся в том, как вы ее просматриваете).Это делает алгоритм экспоненциальным по размеру входных данных.
Однако, если мы ослабим наше обычное правило, что входные данные должны быть представлены эффективно , мы могли бы указать W, используя "унарную" запись;W 1 с на входе вместо двоичного представления.Теперь вы можете утверждать, что, поскольку размер входных данных является полиномиальным в n и W, а не в n и lg W, как раньше, таблица DP также является полиномиальной во входных данных.
Это примерно разница между сильной и слабой NP-жесткостью: если задача слабо NP-жесткая, то алгоритм полиномиального времени (обычно основанный на динамическом программировании) можно найти, если мы укажем унарное кодирование некоторого числового параметра, а нечем обычное двоичное кодирование.