Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
