Перепишите O(N W) через N

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

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

Таким образом, O (NW) - это затраты пространства и времени, где пространство будет для 2d-матрицы и при использовании динамического программирования. Эта задача является частным случаем задачи о рюкзаке.

Я не уверен, как подойти к этому, поскольку я пытался думать об этом, и единственное, о чем я думал, это найти сумму всех весов и просто иметь общий сценарий наихудшего случая. Спасибо


algorithm dynamic-programming discrete-mathematics
person capa_matrix    schedule 14.04.2014    source источник
comment
Этот вопрос кажется не по теме, потому что он относится к Computer Science   -  person    schedule 14.04.2014

Ответы (2)


arrow_upward
1
arrow_downward

Если вес не ограничен, и поэтому сложность должна зависеть исключительно от N, существует как минимум подход O (2N), который перебирает все возможные подмножества из N элементов и вычисляет их суммы.

person Gassa    schedule 14.04.2014
comment
Но как насчет подхода в динамическом программировании, когда сложность пытаются уменьшить. Я понимаю, что, поскольку W неограничен, тогда 2 ^ n будет временем, так как это применимо к упомянутому методу. Если действительно ничего нет? - person capa_matrix; 15.04.2014
comment
@capa_matrix: Согласно Википедии, задача о рюкзаке является NP-полной, если у вас нет других ограничения. Тем не менее, вы можете уменьшить 2 ^ n до 2 ^ (n/2) или лучше (прочитайте связанную статью для некоторых указателей). - person Gassa; 15.04.2014
comment
@capa_matrix Если у вас есть алгоритм, который работает для общих экземпляров суммы подмножества, и время его выполнения зависит только от n, он должен быть экспоненциальным по n, если только P = NP - person Niklas B.; 15.04.2014

arrow_upward
0
arrow_downward

Если вы хотите использовать экспоненциальное пространство, а не полиномиальное пространство, вы можете решить проблему за время O (n 2 ^ (n/2)) и пространство O (2 ^ (n/2)) если вы разделите свой набор n веса на два набора A и B примерно одинакового размера и вычислить сумму весов для всех подмножеств двух наборов, а затем хешировать все суммы подмножеств в A и хешировать W - x для всех сумм x подмножеств B, и если вы столкнулись в хеш-таблице между подмножеством A и подмножеством B, то вы нашли подмножество, сумма которого равна W.

person user2566092    schedule 14.04.2014
comment
@NiklasB Для полиномиального пространства я имел в виду метод грубой силы, заключающийся в проверке всех 2 ^ N подмножеств. Для этого явно требуется только полиномиальное пространство. - person user2566092; 15.04.2014