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?
Best Answer
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.