Is there already an existing data structure for this task?

Question

Algorithms

Hello everyone

There are positive numbers (a little, on average from 1 to 50-70). You need to be able to get a set of numbers from the existing set, the sum of which does not exceed some number N, and the largest of such sums. For example, for the number N = 1200 and the following set {800, 100, 1000, 190 , 150, 1180}, by calling the desired method 3 times, we would get {1000, 190}, {1180}, {800, 100, 150} .

PS; Java NavigableSet has a floor() method that seems to solve this problem, but, for example, for the set of numbers presented above, the sums of all possible combinations without repetitions would have to be written there, which would lead to a combinatorial explosion.

Answer 1

See solving the knapsack problem through dynamic programming .
Construct a two-dimensional array that will say whether the given sum can be collected by the first k objects.
Using it, you can relatively quickly restore all sets with a given amount, and at the same time see what amounts it is possible to collect.