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

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

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

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

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

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

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

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

»
11 лет назад, скрыть # |
← 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...

→ Ответить
»
11 лет назад, скрыть # |
← 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
→ Ответить