Нахождение двух минимальных сумм чисел Опции

[S_lip]

Здравствуйте!
Вот такая задачка:

Дана упорядоченная последовательность N чисел. (2<=N<=200). Каждое число больше 0, но меньше 30000. Нужно из этого ряда найти два набора чисел, величины которых должны быть равны и минимальны. Гарантируется, что эта величина будет меньше 100000. Эту величину нужно выписать.

Примеры:
Дано: 1 2 3 4 5. Группы чисел: 1 2 и 3. Ответ: 3.
Дано: 1 2 5 5 8 10 102. Группы чисел: 5 и 5. Ответ: 5.
Дано: 2 3 4 5. Группы чисел: 2 3 и 5. Ответ: 5.
Дано: 1 3 5 7 13 21. Группы чисел: 1 7 и 3 5. Ответ: 8.
Дано: 1 2 5 8 14. Группы чисел: 1 2 5 и 8. Ответ: 8.


Вот я придумал вот такое решение:
http://img401.imageshack.us/img401/500/20308125la9.png

const
  MaxCount=200;
  MaxSum=100000;
type
  pair=record
    l,r:longint;
  end;
var
  a:array [1..MaxCount] of integer;
  b:array [0..50000] of pair; //чтоб хватило
  f:text;
  n,i,j,k,d:integer;
begin
  assign(f,'file.in');
  reset(f);
  readln(f,n);
  for i:= 1 to n do readln(f,a[i]);
  close(f);

  d:=0;
  repeat
    inc(d);
    b[0].l:=a[d];
    b[0].r:=0;
    i:=1;
    k:=d;

    repeat
      inc(k);
      for j:= 0 to (i-1) do begin
        b[j+i].l:=b[j].l;
        b[j+i].r:=b[j].r+a[k];
        inc(b[j].l , a[k]);
      end;
      j:=1;
      inc(i,i);
      while (j<=i) and (b[j-1].l<>b[j-1].r) do inc(j);
    until(j<=i) or (b[0].l>MaxSum)

  until j<=i;
  
  writeln(b[j-1].l);
end.

Программа перебирает все возможне пары сначало с участием первого числа. Если сумма этих пар больше 100000, а равные величины так и не найдены, то перебирает все возможные пары с участием второго числа и т.д.

Это решение кушает очень много памяти и при большом N вылетает. Возможно, есть более элегантное и правильное решение? =)

[Michael_Rybak]

Его решение оптимально, поэтому твое в лучшем случае имело бы лучшую константу, и такую же асимптотику.

Сам бы делал по-другому и совершенно неочевидно, что это было бы оптимальнее.

Очевидно, потому что твое - экспоненциальное, его - полиномиальное.

Решения, честно говоря, не понял.

Смотри. Как бы мы не выбирали числа для первой и второй суммы, мы никогда не вылезем за 100000 ни в одной из сумм (если вылазим, можно игнорировать такую выборку).

Пусть мы кладем гири на весы, а не даем деньги детям (мне так удобнее).

Заведем массив can_achieve_difference[-100000 .. 100000] of boolean, заполним его false'ами.

Теперь по очереди решим следующие подзадачи:

Какие разницы между левой и правой чашей можно получить, если у нас есть только первая гирька? Только первые две? Только первых три? И т.д.

Чтобы узнать, какие разницы можно получить, используя только первые k+1 гирек (но не обязательно все k+1, конечно), нужно (k+1)-ю гирьку Х добавить ко всем найденым на данный момент разницам, и отнять от всех найденых разниц, а также учесть разницы Х и -Х.

// схематически

fillchar(can_achieve_difference_next_step, false);

can_achieve_difference_next_step[X] := true; // только эта гирька на правой чаше
can_achieve_difference_next_step[-X] := true; // только эта гирька на левой
for i := -100000 to 100000 do
  can_achieve_difference_next_step :=  
    can_achieve_difference[i-x] // на левую чашу?
    or can_achieve_difference[i + x] // на правую?
    or can_achieve_difference[x]; // не используем вообще?
 
move(can_achieve_difference, can_achieve_difference_next_step); 
  // на самом деле, второй массив не нужен, так как старые значения true остаются на месте. но так - понятнее

Как только can_achieve_difference[0] станет равен true, это будет означать, что решение существует.

Такой подход не учитывает, что нас интересует минимальная сумма весов гирек, и не дает возможности восстановить найденое решение. Чтобы это учесть, нужно хранить не только true/false, а еще и минимальный вес и последнюю использованную гирьку.