Subset partition problem variant

Question

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?

Answer 1

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