1005. Куча камней

Имеются n камней с весами w₁, w₂, …, w_n. Необходимо разложить их в две кучки так, чтобы разность весов этих кучек была наименьшей.

Вход. Первая строка содержит количество имеющихся камней n (1 £ n £ 20). Далее следуют веса камней w₁, w₂, …, w_n (1 £ w_i £ 100000), разделенные пробелами (или символами перевода строки).

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

Пример входа

5

5

8

13

27

14

Пример выхода

3

РЕШЕНИЕ

полный перебор

Анализ алгоритма

Расположение камней в одной из кучек будем кодировать последовательностью длины n из нулей и единиц (маской): i - ый элемент последовательности содержит 1, если камень весом w_i присутствует в кучке.

В задаче следует перебрать все возможные расположения камней в кучках. Среди всех расположений находим такое, для которого модуль разностей весов кучек наименьший.

Пусть sum – сумма весов всех камней. Пусть Pile – вес одной кучки. Тогда вес другой кучки sum – Pile, а разность весов кучек составляет | sum – 2*Pile |.

Реализация алгоритма

#include <stdio.h>

#include <math.h>

#define INF 2000000000

int n, i, res, sum;

int Diff, Pile;

int w[20];

int GetWeight(int n)

{

int Weight = 0, ptr = 0;

while(n > 0)

{

Weight += w[ptr++] * (n % 2);

n /= 2;

}

return Weight;

}

int main(void)

{

scanf("%d",&n);

for(i = sum = 0; i < n; i++)

{

scanf("%d",&w[i]);

sum += w[i];

}

res = INF;

for(i = 1; i < (1<<n); i++)

{

Pile = GetWeight(i);

Diff = abs(sum - 2 * Pile);

if (Diff < res) res = Diff;

}

printf("%d\n",res);

return 0;

}