Драгоценные камни (Stone pile 1005).

You have a number of stones with known weights W1…Wn. Write a program that will rearrange the stones into two piles such that weight difference between the piles is minimal.

Исходные данные.

Input contains the number of stones N (1 ≤ N ≤ 20) and weights of the stones W1…Wn (1 ≤ Wi ≤ 100000) delimited by white space (either space characters or new lines).

Результат.

Your program should output a number representing the minimal possible weight difference between stone piles.

Вольный перевод: нужно поделить камни на две кучи с минимальной разницей весов.

Идея алгоритма, который часто предлагают школьники: считываем числа в массив, сортируем его, по одному большому камню кладем в кучи. Просматриваем остальные камни и кладем очередной камень в ту кучу, в которой в этот момент вес камней меньше. Пишем программу, тестируем.

Var a: array[1..20] of integer;

n,i,j,k:integer;

Begin

Readln(n);

For i:=1 to n do readln(a[i]);

For i:=n-1 downto 1 do

For j:=1 to i do

If a[j]>a[j+1] then Begin

k:=a[j];

a[j]:=a[j+1];

a[j+1]:=k;

End;

j:=0;

k:=0;

For i:=n downto 1 do

If j<k then j:=j+a[i] else k:=k+a[i];

Write(abs(j-k));

Readln

End.

Протестируйте программу, меняя число и веса камней. Все ваши тесты проходят?

Придумайте тесты, которые «не пройдут». Не придумали?

Вот один из них: 5 камней (8, 7, 6, 4, 3). Результат программы 2. Суммы 8+4+3=15 и 7+6=13, разница 2. А правильный результат: 8+6=14 и 7+4+3=14, разница и соответственно ответ 0.

Ниже приведено решение Павла Семушина (Самарский лицей информационных технологий) методом динамического программирования. Возможно только с целыми весами камней. Для вещественных весов пришлось бы делать полный перебор. Размер вспомогательного массива определяется значениями весов камней (современные компиляторы допускают такие размеры массивов).

Var

a: array[1..20] of integer;

b: array[0..100000] of integer;

{допустимый размер для компилятора на сайте}

n, i , j, k, s: integer;

Begin

Readln(n);

s:=0;

For i:=1 to n do Begin

Readln(a[i]);

s:=s+a[i];

End;

k:=s div 2;

For i:=k downto 0 do

If i>=a[1] then b[i]:=a[1] else b[i]:=0;

For i:=2 to n do

For j:=k downto 1 do

If (j>=a[i]) and (a[i]+b[j-a[i]]>b[j]) then b[j]:=a[i]+b[j-a[i]];

Write(abs(s-2*b[k]));

End.

Протестируйте эту программу. Теперь даже ваши самые «трудные» тесты пройдут!