2. Динамично оптимиране - братска подялба [8.2.2]
Двама братя трябва да си поделят комплект от n подаръка. Всеки подарък има
стойност цяло положително число. Да се разделят подаръците на две части
със стойности a и b, така, че |a - b| да има най-малка стойност.
Нека сумата от стойностите на всички подаръци е p. Правим масив c с p елемента, като c[i]
= 1 ако i може да се получи
като сума на някои подаръци, в противен случай c[i]
= 0. Решението на задачата ще бъде индекса на най-близкия до p/2 ненулев елемент на c.
Нека стойностите на подаръците да са:
3, 2, 3, 2, 2, 77, 89, 23, 90, 11
Решение.
a = 136, b = 166
Кои подаръци дават стойност a?
Вместо 1 или 0 в елемента c[i] ще пазим номера на подаръка,
последен добавен, за да се получи стойност i.
Решение.
11 + 90 + 23 + 2 + 2 + 3 + 2 + 3 = 136
89 + 77 = 166
Дадени са
камъни с тегла x1,
x2,
x3,..., xn
- цели числа. Напишете
програма, която ще ги подреди в две купчини, така че разликата в
тежестите на купчините да е минимална.
Вход:
Първи ред - числото n (1 <
n < 20). Следват n числа (от 1 до 10000), разделени
с интервал. Входът съдържа много примери, наредени един след друг.
Изход:
За всеки пример от входа се извежда едно число - минималната възможна
разлика в теглата на двете купчини.
Примерен вход:
5
5 8 13 27 14
4
2 3 2 3
Решение:
3
0
Ако
братята са трима? А повече от трима?