How to find biggest sum of items not exceeding some value? For example I have 45 values like this: 1.0986122886681098, 1.6094379124341003, 3.970291913552122, 3.1354942159291497, 2.5649493574615367. I need to find biggest possible combination not exceeding 30.7623.
I can't use bruteforce to find all combinations as amount of combination will be huge. So I need to use some greedy algorithm.
This is an instance of the Knapsack problem. It is NP-hard, so with 45 items, you'll have to use some heuristic algorithm (Hill Climbing, for example) to find an acceptable estimate. To find the optimal solution, you have no other option than to try all possibilities (which is infeasible). Knowledge of your distribution might change that. If many of the items by themselves would exceed the limit, they could be discarded. Or if the limit would be very close to the sum of all numbers, you might need only a combination of up to about 5 items to not be included; 45 choose 5 is still feasible.