Альтернатива динамическому программированию проблем раздела - PullRequest
0 голосов
/ 23 октября 2019

Этот вопрос касается известной проблемы разбиения.

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

Я хотел бы знать, есть ли решение вопроса:" разбить множество на два так, чтобы их разность составляла некоторое значение d "

Возможно, их разность равна, например, 1 или 2.

subset({3,4,9}, diff=2) = [{9}, {3,4}]

, потому что сумма подмножества 1 равна 9, а подмножества два - 7, что дает нам разницу 2, как и хотелось.

Есть ли такая проблема, как эта?

1 Ответ

0 голосов
/ 23 октября 2019

Эта проблема просто эквивалентна сумме подмножества один .
Решите сумму подмножества для sum=overall_sum/2 + d/2, и вы получите необходимые подмножества в качестве решения, а остальные

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...