Суммирование чисел из файла Опции

[Huver]

Задача:
Дано N целых чисел A1, A2 ... An. Требуется найти кол-во различных сумм вида k1A1 + k2A2 + ... + knAn.
Ввод из файла sums.in. В первой строке находится число N, во второй - A1, A2 ... An через пробел.
Вывод в файл sums.out. Вывести одно число - количество различных значений сумм.

Пример 1:
Ввод 1
3
1 1 2
Вывод 1
5

Пример 2:
Ввод 2
5
49 100 98 49 0
Вывод 3
10

Заранее спасибо.

Сообщение отредактировано: Huver - 14.11.2005 22:39

[c-ch]

прошу прощения за поднимание явно древней темы
уточняю условие задачи:
Дано N целых чисел A1, A2, ..., AN. Требуется найти количество различных значений сумм вида k1A1 + k2A2 + ... + kNAN.

Входные данные

Входной файл INPUT.TXT в первой строке содержит число N, во второй - A1, A2, ..., AN через пробел. Ограничения: все числа целые, 1 <= N <= 500, 0 <= Ai <=100, 0 <= ki <= 1.

Выходные данные

В выходной файл OUTPUT.TXT выведите количество различных значений сумм.

т.е., для приведённого примера с числами 1, 1, 2 правильный ответ будет 5, т.к. суммы будут следующие:
0, 1, 2, 3, 4 (все к=0, к1=1 остальные=0, к3=1 остальные=0, 1+2, 1+1+2)

я написал программку, решающую эту задачу, что называется, "в лоб"

program qq;
var a:array[1..500]of integer; {комбинации}
    b:array[1..500]of 0..100; {числа из файла}
    s:array[1..10000] of integer; {суммы}
    n,k,q,z,c:integer;
    f:text;

function Last:boolean;
  begin
  last:=a[1]=n-k+1
  end;

procedure First;
  var i:integer;
  begin
  for i:=1 to k do a[i]:=i
  end;

procedure Next;
  var i,j:integer;
  begin
  j:=k;
  while a[j]=n-k+j do j:=j-1;
  a[j]:=a[j]+1;
  for i:=j+1 to k do a[i]:=a[i-1]+1;
  end;

Function Sum:integer;
  var i,s:integer;
  begin
  s:=0;
  for i:=1 to k do s:=s+b[a[i]];
  Sum:=s;
  end;

Function InSums(x:integer):boolean;
  var i:integer; flag:boolean;
  begin
  flag:=false;
  for i:=1 to c do
      if s[i]=x then flag:=true;
  InSums:=flag;
  end;

begin
assign(f,'input.txt');
reset(f);
readln(f,n);
for q:=1 to n do read(f,b[q]);
close(f);
s[1]:=0;
c:=1; {количество сумм}
for k:=1 to n do
    begin
    First;
    while not Last do
          begin
          if not InSums(Sum) then begin c:=c+1; s[c]:=sum end;
          Next
          end;
    if not InSums(Sum) then begin c:=c+1; s[c]:=sum end;
    end;
assign(f,'output.txt');
rewrite(f);
write(f,c);
close(f)
end.

проблема в том, что этот алгоритм очень трудоёмок и при N=500 вычисления, мягко говоря, затягиваются
у меня же одним из условий является ограничение по времени и памяти - 1 сек и 16 Мб соответственно
прошу помощи у корифеев алгоритмизации
хотелось бы получить рабочий исходник, т.к. времени мало осталось, но буду рад и ценным указаниям (желательно с примерами)
спасибо

[Lapp]

проблема в том, что этот алгоритм очень трудоёмок и при N=500 вычисления, мягко говоря, затягиваются
у меня же одним из условий является ограничение по времени и памяти - 1 сек и 16 Мб соответственно

Этих ресурсов тут во много раз больше, чем достаточно (для тех пределов, которые в условии). Вот эта программка обходится примерно 50 КБ и 0.05 сек на моем ноуте (Turion 1.8 GHz) .

const
  a=100;   {numbers range, 0..a0}
  k=500;   {max number quantity}

var
  n,m,i,j,b: word;
  s: array[0..k*a]of boolean;
  f: text;

begin
  Assign(f,'input.txt');
  ReSet(f);
  ReadLn(f,n);
  s[0]:=true;
  for i:=1 to n do begin
    ReadLn(f,b);
    for j:=(i-1)*a downto 0 do if s[j] then s[j+b]:=true
  end;
  Close(f);
  m:=0;
  for i:=0 to n*a do if s[i] then Inc(m);
  WriteLn(m);
  Assign(f,'output.txt');
  ReWrite(f);
  WriteLn(f,m);
  Close(f)
end.