PartitionProblem - найти оптимальные подмножества

Question

Мне нужно найти оптимальные подмножества после решения проблемы раздела с использованием алгоритма псевдополиномиального времени динамического программирования.

Более конкретно, я не в состоянии понять смысл этого ответа: https://stackoverflow.com/a/890243/1317826

Я не в состоянии понять, как построить оптимальные подмножества из булевой таблицы.

В статье Википедии о проблеме раздела имеет тоже: http://en.wikipedia.org/wiki/Partition_problem

Может кто-то пожалуйста, пролить некоторый свет на это?

Answer 1

Все, что вам нужно, это ответ, который вы отправили.

Прежде всего, при создании таблицы с использованием алгоритма времени псевдо-полиномом не хранить булевы значения (True, если он доступен, в противном случае значение False), но значение элемента, который был добавлен к подмножеству. Затем вы сможете построить подмножество, просто вычитая его из полученной вами суммы.

Так алгоритм:

1. Для каждого номера x_i в наборе:

   1. Набор p(1, x_i) = x_i

   2. Для любого другого поля p(row, sum) установить его x_i если p(row-1, sum-x_i) != 0

2. Так что теперь p(row, sum) = x означает, что мы можем получить sum, принимая некоторые row элементы нашего набора и последний один из них x.

3. После p(some_row, N/2) != 0 вы можете построить подмножество, взяв его значение x и переместившись на p(some_row - 1, N/2 - x) и так далее.

Надеюсь, это прояснит ситуацию.

BTW. Есть ли способ написать латекс в ответах?