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

How to divide N integers into some groups such that the sum of integers of each group does not exceed a given value and the number of groups is minimum possible?
Автор __BaD_mAn__, 6 лет назад, По-английски

We are given two integers N & K and a sequence of N non-negative integers a1 a2 ... aN. We want to divide these numbers into X groups such that the sum of numbers of each group does not exceed K. What is the minimum possible value of X?

Can anyone please describe the approach for this problem? Is it possible to solve this problem in O(N2) or O(NlogN) or O(N) complexity?

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -40 Проголосовать: не нравится

Writing $$$O(N^2)$$$ is enough. (as it includes both $$$O(NlogN)$$$ and $$$O(N)$$$)

→ Ответить
»
6 лет назад, скрыть # |
 
Проголосовать: нравится +28 Проголосовать: не нравится

Given an array of $$$N$$$ integers, is it possible to partition them into two subsets $$$S_1$$$ and $$$S_2$$$ such that the sum of the elements in $$$S_1$$$ equals the sum of the elements in $$$S_2$$$? This is a well-known NP-complete problem (https://en.wikipedia.org/wiki/Partition_problem), meaning that we highly doubt that a polynomial-time solution for it exists.

However, we can reduce this to your problem. Suppose we had a polynomial-time algorithm which solved your problem. Set $$$K=\sum a_i/2$$$, run your algorithm, then check if $$$X = 2$$$; this solves the partition problem in polynomial time.

Thus, if you have found a polynomial-time solution to your problem, then you would have also found a polynomial time solution for the partition problem, and solved one of the Millennium Problems.

So, yeah, I doubt an $$$\mathcal{O}(n^2)$$$ algorithm exists.

→ Ответить