# Find sets of weighted objects to maximize number of sets with weight >= X

I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number of objects.

1). What is a fast and correct algorithm to solve this?
2). Is this NP-complete, hard, or neither?

Ideally, I'd want the left over set of objects that does not add up to x to be maximal as well, but would settle for an understanding of how to solve the problem without this.

• If I understand correctly the input is a collection of $N$ (natural?) numbers $x_1, x_2, \dots, x_N$, plus an additional (natural?) number $X$. Can you clarify what the expected output is? Nov 28 '20 at 23:57
• Yes, apologies. So lets say I have input (2, 7, 8, 3, 11) and X = 10. A possible output is (7, 3), (8, 2), (11). This solution has 3 subsets that achieve a weight >=x, and the goal is to have a solution that maximizes that number--the number of such subsets. So, (8,3) (11) would be suboptimal because (7,2) is not >= x so I'm one subset shy of the optimal number. Nov 29 '20 at 0:05
• So, just you are looking for a partition of \{x_1, \dots, x_n\} into subsets $S_1, S_2, \dots$ such that the number of subsets $S_i$ satisfying $\sum_{x \in S_i} x \ge X$ is maximized. Is this correct? Nov 29 '20 at 0:07
• yes! That's exactly right. And I'd like for the size of the remainder to be maximal as well if that's possible. Nov 29 '20 at 0:09
• Please edit the question to clarify it based on the feedback. Don't just put clarifications in the comments: we want the question to be understandable to future readers without having to read the comments. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to you but also to others in the future. Thank you!
– D.W.
Nov 29 '20 at 0:47

This problem is NP-hard as it can be seen by a reduction from $$3$$-partition.

In the $$3$$-partition problem we are given a (multi-)set $$\mathcal{S}$$ containing $$3n$$ positive integers $$x_1, \dots, x_{3n}$$ and the goal is that of deciding whether there exists a partition of $$\mathcal{S}$$ into $$n$$ sets $$S_1, \dots, S_n$$ of $$3$$ elements each, such that, for each $$i$$, $$\sum_{x \in S_i} x = T$$, where $$T = \frac{1}{n} \sum_{i=1}^{3n} x_i$$.

It is known that this problem remains NP-hard even when each $$x_i$$ is strictly between $$T/4$$ and $$T/2$$. We will therefore restrict to such instances.

To obtain an instance of your problem, it suffices to use the same set of integers $$\{ x_1, \dots, x_{3n} \}$$ (i.e., $$N=3n$$) with $$X = T$$. Clearly, since the sum of any two input elements can be at most $$2 \cdot (\frac{T}{2}-1) < T = X$$, we have that, in any partition $$\mathcal{P}$$ of $$\{ x_1, \dots, x_{3n} \}$$, the number of sets $$S \in \mathcal{P}$$ such that $$\sum_{x \in S} x \ge X$$ can be at most $$N/3 = n$$.

If the answer to the 3-partition instance is "yes", then the same partition $$S_1, \dots, S_n$$ exactly matches this upper bound in the instance of your problem. On the other hand, if the answer to the 3-partition instance is "no", then in any partition of $$\{ x_1, \dots, x_{3n} \}$$ there is at most one set with sum smaller than $$T$$, i.e., there are at most $$n-1$$ sets with sum at least $$T$$.

To summarize: the answer to the instance of $$3$$-partition is yes if and only if the optimal solution to the corresponding instance of your problem has measure at least $$n$$.

Your problem is not NP-complete since it does not belong to NP (since it is not a decision problem). Unless P=NP there is no efficient (polynomial-time) algorithm for your problem.