Как разделить массив на две части максимально близки к равенству?

151

03 мая 2019, 04:10

Есть какие то кучки камней (A1,A2,A3,A4...An) , нужно разделить масив на две части таким образом чтобы разница сумм елементов обоих частей была минимальной.

Я недавно решал задачу "Subset with given sum" используя метод о ранце, так как ваги предметов были малы, но эта задача не таааа,тут не подойдёт этот метод изза того что ограничение на вагу очень большое.

Я знаю про метод Meet-in-the-middle, но так и недопонял как ето тут применить. Как мне решить даную задачу с помощю метода Meet-in-the-middle?

Ограничения:

n = 40
A[i]<=10^8

Приведу еще тест:

5
3 4 5 6 7

Ответ:

Ну вроде так :)

Answer 1

Разбили весь набор с суммой S пополам.

Составили все возможные подмножества первой половины - их 2^20, около миллиона - посильное количество - посчитали и записали суммы подмножеств в массив, отсортировали его

Составили все возможные подмножества второй половины - считаем суммы s2 и по ходу ищем ближайшее к S/2 - s2 бинарным поиском в массиве, полученном ранее (чтобы не работать с дробными, лучше умножить на 2)

Ключевые моменты на Delphi. A[] - массив данных, в Sums[] генерируются все возможные удвоенные суммы первой половины массива. FindClosestIndex бинарным поиском находит индекс значения в Sums, которое вкупе с текущей (удвоенной) суммой csum из второй половины даёт лучшее приближение к общей сумме S

  //обрабатывает первую половину массива
  procedure GenSums(ix, imax: Integer; csum: Int64);
  begin
    if ix >= imax then begin
      Sums[cnt] := csum;
      inc(cnt);
      Exit;
    end;
    GenSums(ix + 1, imax, csum);
    GenSums(ix + 1, imax, csum + Int64(2) * A[ix]);
  end;
  //обрабатывает вторую половину массива, проверяя пары с суммами первой
  procedure CheckSums(ix, imax: Integer; csum: Int64);
  var
    k: Integer;
  begin
    if ix >= imax then begin
      k := FindClosestIndex(S - csum, Sums);
      Best := Min(Best, Abs(S - (Sums[k] + csum)));
      Exit;
    end;
    CheckSums(ix + 1, imax, csum);
    CheckSums(ix + 1, imax, csum + Int64(2) * A[ix]);
  end;
Примеры выдачи:
20 40 32 83 10 32 13 57 35 
Sum=322 Diff=0
22 70 6 
Sum=98 Diff=42
86 34 74 25 28 
Sum=247 Diff=7