I have a specific subtask for which I have problems with the optimal solution. This problem is similar to a group of sums of subsets of tasks, as well as problems of filling up space, but I have not seen this specific problem anywhere. I don’t necessarily need an optimal solution (since I am relatively sure that it is NP-hard), but an effective and fast approximation will certainly be enough.
Objective: . Given a list of positive integers, find the smallest number of disjoint subsets containing the entire list of integers, where each subset is summed with a smaller N. Obviously, no integer in the original list can be greater than N.
In my application, I have many lists, and I can combine them into matrix columns as long as they fit into the matrix together. For downstream purposes, I would like to have as little “wasted” space in the resulting dangling matrix, hence the similarity of the space.
So far I have been using the greedy approach, processing from the largest integers down and finding the largest integer that fits into the current subset under the limit N. As soon as the smallest integer no longer fits into the current subset, I move on to the next subset similarly until until all numbers are exhausted. It almost certainly does not find the optimal solution, but it is the best that I could come up with quickly.
BONUS . My application actually requires lots where there is a limit on the number of subsets in each lot (M). Thus, the big problem is to find the smallest parties, where each party contains M subsets, and each subset adds up to less than N.
source
share