Knapsack? Problem

Revision en2, by grimalk, 2015-12-13 21:35:04

Statements are something like so: Given n 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 Statements (Also russian only)

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

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)