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

[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 вылетает. Возможно, есть более элегантное и правильное решение? =)

[andriano]

Так и не получил ответа на вопрос:

И так же по поводу эвристик:
Какой именно из двух ваиантов тебе нужен?
1. Программа ВСЕГДА находит нужное решение. Сама программа при этом наиболее проста, но работать может до конца существования Вселенной (ну или, по крайней мере, до физического износа компа).
2. Программа, время работы которой ограничено. При этом она может выдать не то решение, которое нужно (т.е. не минимальное) или же совсем ничего не найти.

Но предполагаю, что второй вариант.
Исходя из этого я и предложил следующий алгоритм, являющийся центральной частью программы:
1. Написать процедуру, которая бы решала задачу в полном объеме, но только для части массива от 1 до K-го элемента.
2. Последовательно вызывать эту подпрограмму для упорядоченного массива, увеличивая число K (начинать с 2).

Далее я предположил, что такое решение будет укладываться в приемлемое время, вероятно, для К менее 12 (т.е. 10 шагов от 2 до 11).

По поводу самого перебора примерно так:
M - максимальная сумма, присваиваем 100000
- перебор по К от 2 до N
-- перебор по всем возможным группам (1-я группа) с количеством элементов от 1 до К-1 (в пределах первых К элементов)
--- в случае, если сумма чисел в группе не больше М, то
---- перебор по всем возможным группам (2-я группа), которые можно сформировать из оставшихся элементов (в пределах первых К)
----- сравнение сумм чисел в группах, если равны, то запоминаем и переопределяем М новой суммой-1

PS. Алгоритма, который предлагаешь ты, я так и не понял.

Сообщение отредактировано: andriano - 29.12.2007 14:37