1
$\begingroup$

Hello, I'd like to know the name of the problem (or a similar problem) that I state below:

Suppose we have a finite set of positive integers. I need to find all the subsets of integers whose sum is less than a constant C and I'd like these sets to be maximal: such that adding any other integer to that set would cause it to overgrow the constant C.

It seems to be fundamental problem and there should be a name for it!

Any ideas?

Improve this question
$\endgroup$
5
  • $\begingroup$ Sounds like the knapsack problem. $\endgroup$
    – Chris Aholt
    Commented Mar 4, 2011 at 16:18
  • 1
    $\begingroup$ The 0-1 knapsack problem (en.wikipedia.org/wiki/Knapsack_problem) asks to find the maximum achievable sum in the situation you describe. $\endgroup$
    – Emil Jeřábek
    Commented Mar 4, 2011 at 16:18
  • $\begingroup$ While this is essentially contained in the previous comment, the additional key-word 'subset sum problem' might also be of help, see en.wikipedia.org/wiki/Subset_sum_problem $\endgroup$
    – user9072
    Commented Mar 4, 2011 at 16:44
  • $\begingroup$ You should be able to 'efficiently' answer this problem with dynamic programming, since at every point either you have a solution or one or more elements of the set can be added to the collection. I quote "efficiently" because the number of subsets is likely to be large and so even if the algorithm is linear in the size of the output it could be quite time-consuming. A small modification to the algorithm would allow multisets rather than sets. $\endgroup$
    – Charles
    Commented Mar 7, 2011 at 0:16
  • $\begingroup$ Here is a solution implemented in Python: docs.google.com/document/d/… Regards, Auden RovelleQuartz $\endgroup$
    – user2759990
    Commented Sep 17, 2013 at 19:07

1 Answer 1

Reset to default
2
$\begingroup$

Since you also ask for similar problems, this is a (partial) answer:

As mentioned in the comments your question is related to the Knapsack and/or Subset Sum problem, which are well-known problems in Combinatorial Optimization.

As said, solving the Knapsack problem would mean to determine the largest sum $s\le C$ you can obtain. To ask for any specific $n$ whether there is a subset with sum $n$ would be (a form of) the Subset Sum problem.

Now, you ask for the sets and not the value of the sum, so your question is closer to the Inverse Problem associated to these problems; that is the determination of the collection of all solutions to the above problems, i.e., all sets that sum to $s$ (or $n$). (Note: Inverse Problem is an actual technical term.)

As said, this is not exactly what you asked for but quite similar; in particular, if you would solve Inverse Subset Sum for all $n \le C$ you would not get what you want as the maximality condition is omitted.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .