|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Victor Petrov 2:5030/744.113 25 May 2001 11:22:52
To : Ihor Bobak
Subject : a[i1]+a[i2]+...+a[ik] = N*p
--------------------------------------------------------------------------------
В письме от Ihor Bobak к All от Четверг Май 24 2001 00:20 писалось:
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> Кто нибудь знает нормальный алгоритм решения этой задачи?
Стандаратная задача на динамическое программирование. Для любого k, 1<=k<=N, мы
находим множество остатков по модулю N, который можно получить суммированием
a[i], где 1<=i<=k. Для k=1 оно находится состоит из одного элемента - a[1] mod
N. Переход от k к k+1 тоже осуществляется легко: прибавляем ко всем элементам
множества, полученного на шаге k, a[k+1], и добавляем эти элементы к нашему
множеству. Когда k=N, мы узнаем, можно ли получить 0. Стандартным способом
(запоминание предыдущего шага) можно восстановить нужное решение.
Программка примерно такая (пишу сходу, поэтому могут быть мелкие баги).
program Macro;
const MaxN=10000;
var A:array[1..MaxN] of integer;
P:array[0..MaxN-1] of integer;
N,i,k:integer;
begin
readln(N);
for k:=1 to N do
begin
read(A[k]); A[k]:=A[k] mod N;
end;
for i:=0 to N-1 do P[i]:=0;
for k:=1 to N do
begin
P[A[k]]:=k;
for i:=0 to N-1 do
if P[i]>0 then P[(i+A[k]) mod N]:=k;
end;
if P[0]=0 then write('NO SOLUTION') else
begin
write('SOLUTION: ');
i:=0;
repeat
write(P[i],' '); i:=(i-A[P[i]]) mod N
until i=0
end
end.
Victor
--- EOS v0.70
* Origin: Свобода - это познанная необходимость. (2:5030/744.113)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
