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

[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]

Задача переборная. Поэтому основная идея в решении - сократить перебираемое количество вариантов.
Для начала я бы написал функцию, которая осуществляет перебор всех возможных групп в массиве длины N, где N - входной параметр (массив может быть и глобальный).
Затем отсортировал массив чисел по возрастанию и стал последовательно вызывать функцию перебора, для возрастающих значений N, начиная с 2.
Если за некоторое количество шагов (думаю, не больше 10) искомое решение не найдено, попытался бы применить эвристику (какую - пока не знаю).

В твоем решении не разбирался, но мне непонятно две вещи:
1. Почему именно пары? Ведь в условии, если я правильно его понял, возможны группы из произвольного количества элементов.
2. Зачем хранить пары? Это явно нерациональное использование памяти. У нас ведь переборная задача. Увеличение объема вычислений в 2-3 раза совершенно некритично. Поэтому не грех вычислять суммы прямо внутри цикла, нигде их не храня. Сохранять имеет смысл только наилучший из найденных ваиантов.


Через некоторое время.

Пожалуй, эвристики или, по крайней мере, некоторые из них лучше использовать ДО перебора. В частности, они могут помочь найти решение, не являющееся минимальным, но существенно сокращающее объем дальнейшего поиска.

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

Да, и еще:
Перебор рано заканчивать, если найдено решение, при котором в обеих группах более одного элемента, - необходимо продолжить его до тех пор, пока в рассмотрении не будет участвовать максимальное число, не превосходящее эту сумму.

Сообщение отредактировано: andriano - 27.12.2007 18:44