|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 24 May 2001 02:03:29
To : All
Subject : Re: a[i1]+a[i2]+...+a[ik] = N*p
--------------------------------------------------------------------------------
"Ihor Bobak" <ihor@bulgaria.com> wrote in message
news:9eh5hk$1enu$1@gavrilo.mtu.ru...
> Есть такая задача: дано масив N чисел a[1], a[2],..., a[N].
> Из него нужно выбрать такое подмножество из k<=N элементов, чтобы
> a[i1] + a[i2] + ... + a[ik] делилось на N (если такое подмножество
> существует вообще)
> Так как N может быть довольно большим (около 10000), то перебор в
> лоб (то есть "брать элемент - не брать") дающий сложность О(2^N) есть
> недопустимым.
Пару месяцев назад проходила очень близкая к данной задача
но "попроще" - определить множество чисел, сумма которых равна N.
Hа практике хорошо построенный перебор с отсечением явно
неправильных вариантов позволяет решить такую задачу
достаточно быстро.
Для целых чисел можно сделать алгоритм прямо для данной
задачи сложности N^3.
1) Определяем битовый массив, который будет хранить
всевозможные суммы элементов. Элемент массива true,
если существует сумма (вернее сумма%N) равная индексу.
bool s[N];
2) Инициализируем. Все элементы false, поскольку нет элементов.
for(int i=0; i<N; i++) s[i]=false;
2) Для каждого числа из множества (я предположил, что не всегда
число элементов соответствует сумме)
int i;
for(i=0; i<K; i++){
2.1) Делаем циклический сдвиг массива на a[i] элементов, что
соответствует всем предыдущим суммам плюс данный элемент
bool r[N];
for(int j=0; j<N; j++) r[(i+a[i])%N]=s[i];
2.2) Объелиняем с исхожным массивом, ведь можем этот элемент
и не добавлять
for(int j=0; j<N; j++)if(r[j]) s[j]=true;
2.3) Добавляем данный элемент.
s[a[i]%N] =true;
2.4) Проверяем, есть ли сумма кратная N, т.е. нулевой элемент (или N%N-й,
кому что нравится :) и если да, то заканчиваем
if(s[0]) break;
}
3) Если цикл закончен по 2.4, то известно, что a[i] входит в сумму,
поэтому перейдем к аналогичной задаче для суммы N-a[i] и первых
i-1 элементов. Делается внешним циклом или рекурсией.
Таким образом сложность в случае неуспеха - K*N,
в случае успеха - K^2*N.
Hекоторого ускорения возможно можно достичь
пересортировкой элементов по убыванию a[i]%N.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: a[i1]+a[i2]+...+a[ik] = N*p 
