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.
On
This problem can be phrased as a zero-one assignment problem, and solved with a linear programming package, such as GLPK, which can handle integer programming problems. The problem is to find binary variables x[i] such that the sum of x[i]*w[i] is as large as possible, and less than the prescribed limit, where w[i] are the values which are added up.
My advice is to use an existing package; combinatorial optimization algorithms are generally very complex. There is probably a Python interface for some package you can use; I don't know if GLPK has such an interface, but probably some package does.
On
You can try to find approximate solution:
Multiply your floats by appropriate number (for example, 100), do the same for sum.
Round floats to the nearest integers (or Ceil them to larger integers)
like Round(1.0986122886681098 * 100) = 110
Solve subset sum problem for integers with DP
Check that sum of floats doesn't excess the limit
(due to rounding errors)
If you have a lot of very close float numbers, you might want to refine solution with optimisation algorithms (like mentioned Hill Climbing)
On
What you search for is the knapsack problem I guess. Does this solution help you?
http://rosettacode.org/wiki/Knapsack_problem/Unbounded/Python_dynamic_programming
Have a look at the solution under "1.2 DP, single size dimension". I think this is not brute force. You should be able to adapt it to your problem.
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.