grimalk's blog

Knapsack? Problem
By grimalk, history, 8 years ago, In English

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. :]

  • Vote: I like it
  • +13
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
8 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

An approach would be:

Do a knapsack where the limit of the knapsack would be half the total sum of the elements. If the result yields exactly half the total sum, it means that there is a subset that sums to this half. And, obviously, if there is one that sums to half the total sum, there is another one that sums to the other half.

I know this is approach doesn't have the complexity you asked... I'm curious to know about it too...

→ Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it +7 Vote: I do not like it

Note: number of different values of a[i] is O(sqrt(N)) because sum is equal to 2 * n.

u - uniq values in A
cnt[i] - number of occurrences u[i] in A

for i, for x
   int y = x + u[i]
   if (dp[x] != 0 && dp[y] == 0)
      if (prev[y] != u[i] || dp[x] + 1 <= cnt[j])
         d[y] = d[x] + 1
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's exactly what I was looking for.

    Implemented it in C++, worked totally fine. Even though you had some typos in your solution, I've got your point.

    Big thanks to you! :]

    → Reply