Найдите, существует ли какая-либо возможная комбинация для следующего: - PullRequest
1 голос
/ 13 июля 2011

Мне дано N чисел, n 1 , n 2 , n 3 , n 4 ,…, n N (всеположительны).Наконец, мне дают число K в качестве входных данных.

Меня спрашивают, можно ли найти какую-то возможную комбинацию по n 1 , n 2 ,…, n N так, что сумма равна K ,т.е. найти коэффициенты a , b , c ,…, n такие, что:

a · ‍ n 1 + b · ‍ n 2 +… + n · ‍ n N = K

где a , b , c ,…, n может принимать любое целое значение от 0 до K .

Нам просто нужно выяснить, существует ли такая комбинация.

Я думал о том, чтобы установить пределы для экстремальных значений a , b ,…, n .Например, a может быть ограничен как: 0 ≤ a ≤ этаж ( K / ‍ a ).Аналогично, определения диапазонов для b , c ,…, n .Однако этот алгоритм в конечном итоге оказывается O ( n n -1 ) в худшем случае.Эта проблема похожа на проблему с упаковкой в ​​бункер?Это NP завершено?

Пожалуйста, помогите мне с лучшим алгоритмом (я даже не уверен, что мой алгоритм корректен !!).

Ответы [ 3 ]

0 голосов
/ 13 июля 2011

Это просто еще один вариант проблемы с рюкзаком (см. Раздел «неограниченный рюкзак»), такой же NP-полный и сложный, как и другие версии.

Конечно, если Kмала, вы можете использовать решение для динамического программирования, и если N мало, хорошо работает и тщательный поиск.

0 голосов
/ 13 июля 2011

Это целочисленная программа, поэтому, если у вас есть доступ к солверу, я бы порекомендовал вам профилировать его производительность и посмотреть, работает ли он для вас.

0 голосов
/ 13 июля 2011

Это решение предполагает, что числа n1, n2, ... nN являются целыми числами (или что они имеют "наименьший общий делитель")


У меня есть алгоритм O (K * N) (спасибо, что отсутствует за исправление). Идея - немного динамического программирования, немного Сита Эратосфена.

Начните с создания списка L из K + 1 логических значений. L[i] верно, если вы можете «построить» число i (подробнее об этом позже). Все значения L инициализируются как false, кроме L[0]==true

Начните с первого номера n1. Для каждого значения i от 1 до K проверьте, если L[i-n1]==true. Конечно, если i-n1<0, то поступайте так, как если бы L[i-n1]==false. Если L[i-n1]==true, тогда измените L[i] на true. Теперь у вас есть L[n1]==true, L[2*n1]==true, L[3*n1]==true ...

Что теперь означает L? L представляет числа в [0..K], которые могут быть построены только с n1. Если L[K]==true, поздравляю, есть решение, построенное только с n1!

Возьмите число n2 и сделайте то же самое. Для каждого значения i от 1 до K, такого, что L[i]==false, проверьте, если L[i-n2]==true. Если это так, измените L[i] на true.

Что теперь означает L? L представляет числа в [0..K], которые могут быть построены с n1 и n2. Если L[K]==true, поздравляю, есть решение, построенное только с n1 и n2!

Если после заполнения L всеми значениями N L[K]==false, ваша проблема не решена.


Проблема с динамическим программированием заключается в том, что всегда сложно найти решение, когда вы доказали, что он существует ... Вам нужен еще один список S, такой, что S[i] описывает, какие коэффициенты необходимы для "построения" я. (существует только если L[i]==true конечно)

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