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__

Автор __BaD_mAn__, 4 года назад, По-английски

We are given two integers N & K and a sequence of N non-negative integers a₁ a₂ ... a_N. 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(N²) or O(NlogN) or O(N) complexity?

__BaD_mAn__
4 года назад
4

Комментарии (4)

Написать комментарий?

traviscott

4 года назад, # |

-40

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

→ Ответить

Shisuko

4 года назад, # |

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

→ Ответить

mango_lassi

4 года назад, # ^ |

You lose some "hardness" with that reduction. The partition problem is only weakly NP-complete, meaning you can solve it in polynomial time to the sum of $$$a_1, \dots, a_n$$$. The problem here is in fact the Bin packing problem, which is strongly NP-complete.

→ Ответить