|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 24 May 2001 20:42:26
To : Ihor Bobak
Subject : Re: a[i1]+a[i2]+...+a[ik] = N*p
--------------------------------------------------------------------------------
23 Май 01 23:20, you wrote to all:
IB> Есть такая задача: дано масив N чисел a[1], a[2],..., a[N].
IB> Из него нужно выбрать такое подмножество из k<=N элементов, чтобы
IB> a[i1] + a[i2] + ... + a[ik] делилось на N (если такое подмножество
IB> существует вообще)
IB> Так как N может быть довольно большим (около 10000), то перебор в
IB> лоб (то есть "брать элемент - не брать") дающий сложность О(2^N) есть
IB> недопустимым.
IB> Кто нибудь знает нормальный алгоритм решения этой задачи?
Как я её решал:
1) все a[i] если >N, то a[i]:=a[i] mod N;
2) все a[i] записываем как значение и кол-во, для экономии памяти.
10000 - это можно хранить как
Array[0..9999] of LongInt, т.е. для каждого числа из [0..n-1] его кол-во
3) Я делал переборчиком, т.е. надо подобрать сумму N, если их
перебирать с самых больших, впринципе найти можно.
Ещё была какая-то китайская теорема (всмысле она в прямом смысле китайская, не
в переносном), по ней что-то там определялось, но я счас не вспомню.
Andrey
... ... лети, ласточка, только не залетай.. ;-))
--- GoldED+/386 1.1.4.7
* Origin: Всё фигня кроме пчёл,хотя пчёлы,если подумать,тоже фиг (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
