Задача на рюкзак?

Revision ru1, by grimalk, 2015-12-13 21:37:56

Условия легко сводятся к таким: Дано число 1 ≤ n ≤ 105 и n целых чисел 1 ≤ ai ≤ n,

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

Условия очень похожи на рюкзак, но я умею решать эту задачу только жадно. В разборе написано, что задачу можно решить каким-то рюкзаком за .

Линк на Разбор и на Условия (задача C)

Надеюсь, вы поможете мне решить эту задачу. :]

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English grimalk 2015-12-13 21:38:19 9 Tiny change: ' problem [Statements' -> ' problem [(Task C) Statements'
ru1 Russian grimalk 2015-12-13 21:37:56 677 Первая редакция перевода на Русский
en3 English grimalk 2015-12-13 21:36:10 15 Tiny change: ':\nGiven $n$ and an a' -> ':\nGiven $1 \le n \le 10^5$ and an a'
en2 English grimalk 2015-12-13 21:35:04 8
en1 English grimalk 2015-12-13 21:33:34 822 Initial revision (published)