Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
Sounds like the knapsack problem. –  Chris Aholt Mar 4 '11 at 16:18
1  
The 0-1 knapsack problem (en.wikipedia.org/wiki/Knapsack_problem) asks to find the maximum achievable sum in the situation you describe. –  Emil Jeřábek Mar 4 '11 at 16:18
    
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 –  quid Mar 4 '11 at 16:44
    
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. –  Charles Mar 7 '11 at 0:16
    
Here is a solution implemented in Python: docs.google.com/document/d/… Regards, Auden RovelleQuartz –  user2759990 Sep 17 '13 at 19:07

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.