1
$\begingroup$

Given a set S of integers, the task is to partition the set into subsets such that:

  • Total number of partitions is maximized
  • Each partition has sum at least K

This looks like a variant of bin-packing problem, in which the bin has to filled upto a minimum capacity and the objective is to maximize the number of bins. I looked up the solutions of bin-packing problem, turned out ffd was the best approximation solution to it.

Could someone please tell me how to approach the partition problem?

$\endgroup$
2
$\begingroup$

For its complexity, note $N$ the sum of all your integers. Then, the number partitioning problem injects itself into your problem with $K=\frac{N}{2}$

I found this paper which deals with almost your problem. It aims to maximise the number of bins used, but instead of working with each partition must have a sum of at least $K$, you have each partition cannot be completed with another item.

Edit: Another user already asked almost the same question: https://scicomp.stackexchange.com/questions/8216/bin-packing-maximise-number-of-bins-fukubukuro-problem

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.