Является ли следующая проблема в NP-Complete или P?
Входные данные: набор S положительных целых чисел {a1, a2, ..., an) и положительное целое число M
Вопрос: существует подмножество S' множества S такое, что сумма всех элементов S' равна M-1, M или M+1.
Я предполагаю, что он находится в NP-Complete и связан с суммой подмножества. Однако мне трудно сократить сумму подмножества до этой проблемы.
Сложность суммы подмножества с несколькими целями
Ответы (1)
Это NP-полное. Учитывая экземпляр суммы подмножества
Найдите подмножество {x1, ... xn} с суммой X
Рассмотрим следующий пример вашей проблемы
Найдите подмножество {4 * x1, 4 * x2,..., 4 * xn} с суммой 4*X, 4*X-1 или 4*X + 1
Учитывая делимость на 4, становится ясно, что любое подмножество, сумма которого равна 4*X, 4*X-1 или 4*X + 1, на самом деле должна давать в сумме 4X. Но тогда это тривиально дает решение исходной проблемы суммы подмножества путем деления на 4.
person
circular-ruin
schedule
09.11.2015
