Алгоритмы динамического программирования для задачи о рюкзаке дают точное решение за время O(nf*) или O(nB). Если величины f* и B не ограничена сверху никаким полиномом (то есть имеются большие коэффициенты), то эти псевдополиномиальные алгоритмы не является полиномиальными.
Однако, существует общий метод (который условно можно назвать «масштабированием»), позволяющий перейти к задаче с небольшими коэффициентами в целевой функции, оптимум которой не сильно отличается от оптимума исходной задачи.
Если мы отмасштабируем коэффициенты c1,…,cn, поделив нацело их на некоторый параметр scale, решим «отмасштабированную» задачу, и затем снова умножим коэффициенты на параметр scale, то очевидно, что мы получим допустимое решение исходной задачи и абсолютная погрешность стоимости «округленного и восстановленного» набора не превосходит величины n⋅scale.
Если потребовать, чтобы эта величина не превосходила ε1+εf∗, то получим, что каждое допустимое решение исходной задачи отличается от решения «отмасштабированной» задачи не более, чем на эту же величину.
Обозначая оптимум «отмасштабированной» задачи через f˜, получаем, что f˜≥f∗−ε1+εf∗=f∗(1+ε), то есть оптимум «отмасштабированной» задачи отличается от оптимума исходной задачи не более, чем в 1+ε раз.
При этом величина значение оптимального решения для «отмасштабированной» задачи уменьшается не менее, чем в scale раз по сравнению с исходной. И таким образом, для отмасштабированной задачи, версия алгоритма, ориентированная на отбор «самых легких решений» будет работать существенно меньшее время.
Однако проблема состоит в том, что в момент масштабирования мы не знаем величины оптимума f*, и не можем выбрать коэффициент scale, который, чтобы решение было 1+ε-оптимальным, не должен превышать εf∗n(1+ε), с одной стороны, с другой — желательно максимально приблизить его к этой оценке, чтобы уменьшить коэффициенты в задаче.
Поэтому, важное наблюдение состоит в том, что вместо f* можно рассматривать нижнюю оценку f*, обозначим ее flb, и выбирать параметр масштабирования scale=εflbn(1+ε) тогда все вышеизложенные соображения о точности «отмасштабированного» решения сохранят силу.
Таким образом, стоит задача выбора нижней оценки flb, которую можно найти быстро с одной стороны, и желательно чтобы она была как можно ближе к f*, так как это даст возможность увеличить коэффициент scale, и тем самым, сильнее уменьшить коэффициенты c1,…,cn и время выполнения алгоритма. Таким образом, общая схема алгоритма, представлена как процедура «knapsack_ptas_generic», которой на вход, кроме обычных параметров рюкзака, передают функцию «f_lower_bound», используемую для получения нижней оценки стоимости решения.
Осталось найти такую функцию. Например, можно рассмотреть тривиальную аппроксимацию ncmax≥f∗≥flb≡cmax,, где cmax=maxici; и получим функцию «knapsack_ptas_trivial».
Какова сложность этого алгоритма? Она, есть величина O(nf˜). Учитывая, что f∗≤ncmax, а f˜≤ncmaxscale, получаем оценку сложности алгоритма «knapsack_ptas_trivial»: O(nf˜)=On2cmaxscale=On3(1+ε)ε=On3ε.
Можно ли улучшить эту оценку? Ответ на этот вопрос положителен.
Для этого рассмотрим менее наивную аппроксимацию величины f*, используя задача о рюкзаке: жадный алгоритм, дающий точность не хуже чем в два раза.
Используя эту оценку, получаем функцию «knapsack_ptas_nontrivial» Аналогично получаем оценку сложности для этого алгоритма: O(nf˜)=OnfGscale=On2(1+ε)ε=On2ε.
