Доказательство решения проблемы находится в NP

Question

Я читаю CLRS, пытаясь научиться самостоятельно и найти этот раздел.

Я пытаюсь решить и на самом деле не имею решения для обращения.

Позволяет сказать, как вход у вас есть: x1, x2, x3, ..., xn m1, m1, m3, ... mn M1 and M2

Тогда вы должны вывести: A partition into two disjoint subsets S, T (so the intersection is an empty set) so that the sum of each mk (1<=k<=n) of all elements in S is <= M1 and the sum of each mk (1<=k<=n) of all elements in T is <= M2, so that the total value sum of all (xk's in S) + (xk's in T) is maximized. where (1<=k<=n)

Я пытаюсь доказать, что он находится в НП. Я столкнулся с похожим вопросом, когда я проходил динамическое программирование, полагаю, что это было для рюкзака. Но это кажется немного сложнее. Я пишу на бумаге для лома, но, похоже, нет. Это для личного интереса.

Answer 1

Давайте это как вариант решения:

Есть раздел S, T такой, что S и T не пересекаются, общий вес S < = M1, общий вес T < = M2 , и полное значение S∪T> = Y?

(я перефразировать его «вес» и «значение» там, чтобы сделать подключение к котомке более очевидным)

Теперь это в НП?

Да. Существует несколько способов показать членство в NP, самым простым, вероятно, является такой способ: есть свидетель, который позволит нам проверить (в полиномиальное время), что ответ ДА ​​был правильным. Свидетелем является только пара S и T. Для проверки здесь не нужны никакие трюки, просто проверьте все условия, упомянутые в проблеме.

Это также NP-Complete, потому что он решит экземпляр для ранца. Эта проблема похожа на наличие двух рюкзаков, просто сделайте размер одного из них нулевым и вернитесь к обычным ранцам.