|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ihor Bobak 2:5020/400 24 May 2001 00:20:59
To : All
Subject : a[i1]+a[i2]+...+a[ik] = N*p
--------------------------------------------------------------------------------
Есть такая задача: дано масив N чисел a[1], a[2],..., a[N].
Из него нужно выбрать такое подмножество из k<=N элементов, чтобы
a[i1] + a[i2] + ... + a[ik] делилось на N (если такое подмножество
существует вообще)
Так как N может быть довольно большим (около 10000), то перебор в
лоб (то есть "брать элемент - не брать") дающий сложность О(2^N) есть
недопустимым.
Кто нибудь знает нормальный алгоритм решения этой задачи?
Оговорюсь сразу: никакое a[i] не равно по модулю N
(иначе задача решается просто - искомое подможество состоит
из одного элемента), и вообще без ограничения общности можно
считать, что a[i] < N.
Примеры:
N=5, a[] = {1,1,2,3,3} - искомое подмножество 1+1+3=5 делится на 5 (один
вариант решения), 2+3=5 делится на 5 (другой вариант)
N=8, a[] = {5,5,5,5,5,5,5,5} - искомое подмножество = все числа a[],
так как их сумма (=40) делится на 8; больше решений нет;
N=8, a[] = {6,7,7,7,7,7,7,7} - искомое подмножество = 6+7+7+7+7+7+7=48
делится на 8;
--- ifmail v.2.15dev5
* Origin: MTU-Intel ISP (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
