Изменения
описание сведения
<math>f(S,s) = ((S,S),s,s) \,</math>
</p>
То есть, для каждого числа <math>q \in S</math> создадим предмет <math>(q,q)</math> с весом и стоимостью, равной значению числа.
А значения <math>c</math> и <math>p</math> возьмем равными <math>s</math>.
*Очевидно, <math>f~</math> работает за полиномиальное от длины входа время.
*Если исходная [[NP-полнота задачи о сумме подмножества|задача о сумме подмножества]] имела решение <math>S'</math>, то набор пар <math>P'</math> с весами, равными числам из <math>S'</math>, будет решением задачи о рюкзаке.
*В обратную сторону - аналогично.
