Блог пользователя grimalk

Задача на рюкзак?
Автор grimalk, история, 9 лет назад, перевод, По-русски

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

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

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

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

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

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
← Rev. 5   Проголосовать: нравится +7 Проголосовать: не нравится

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
→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить