1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Steven
    Nov 28 '20 at 23:57
  • $\begingroup$ 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. $\endgroup$
    – wbarts
    Nov 29 '20 at 0:05
  • $\begingroup$ 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? $\endgroup$
    – Steven
    Nov 29 '20 at 0:07
  • $\begingroup$ yes! That's exactly right. And I'd like for the size of the remainder to be maximal as well if that's possible. $\endgroup$
    – wbarts
    Nov 29 '20 at 0:09
  • 1
    $\begingroup$ 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! $\endgroup$
    – D.W.
    Nov 29 '20 at 0:47
1
$\begingroup$

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.

$\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.