1005 Timus answer/Решение задачи 1005


№1005
http://acm.timus.ru/problem.aspx?space=1&num=1005
ЖМИ ДАЛЕЕ>>>

РЕШЕНИЕ [C++ ] :


#include <iostream>
#include <stdlib.h>
 
using namespace std;
 
int a[20], n, _min=99999999;
 
int rec (int k1, int k2, int x)
{
 if (x == n)
 {
  if (_min > abs(k1-k2))
   _min = abs(k1-k2);
 }
 else
 {
  rec (k1+a[x], k2, x+1);
  rec (k1, k2+a[x], x+1);
 }
 return 0;
}
 
int main ()
{
 //freopen ("1.txt", "r", stdin);
 int i;
 cin >> n;
 for (i = 0; i < n; i++)
  cin >> a[i];
 rec(0, 0, 0);
 cout << _min;
 return 0;
}

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

Ограничение времени: 2.0 секунды
Ограничение памяти: 16 МБ
У вас есть несколько камней известного веса W1, …, Wn. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.

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

Ввод содержит количество камней N (1 ≤ N ≤ 20) и веса камней W1, …, Wn (1 ≤ Wi ≤ 100 000) — целые, разделённые пробельными символами.

Результат

Ваша программа должна вывести одно число — минимальную разность весов двух куч.

Пример

исходные данныерезультат
5
5 8 13 27 14

3
Источник задачи: Чемпионат УрГУ 1997
Ярлыки: