Knapsack? Problem

Правка en4, от grimalk, 2015-12-13 21:38:19

Statements are something like so: Given 1 ≤ n ≤ 105 and an array of n integers 1 ≤ ai ≤ n,

Needed answer "NO" if this is not possible to divide the array into two groups of same sum or answer "YES" and print all numbers in first group and second group.

The task sounds similar to knapsack problem, and I know only the greedy approach this problem, but I know that this should be possible (according to problem editorial) to solve it with with knapsack approach.

Link to Editorial (Russian only) and to problem (Task C) Statements (Also russian only)

I hope you will be able to help me. :]

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский grimalk 2015-12-13 21:38:19 9 Tiny change: ' problem [Statements' -> ' problem [(Task C) Statements'
ru1 Русский grimalk 2015-12-13 21:37:56 677 Первая редакция перевода на Русский
en3 Английский 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 Английский grimalk 2015-12-13 21:35:04 8
en1 Английский grimalk 2015-12-13 21:33:34 822 Initial revision (published)