Given a set of numbers, get the maximum 10 number average below a certain threshold

As an input, my program accepts a big set of numbers (often times more than 30) and a maximum threshold. I'm trying to get the maximum average between 10 of those numbers below that threshold (the numbers used in that average are also returned).

Right now, I'm testing all 10 number combinations, recording them and their average in a list and getting the maximum average from that list.

As you know, though, when the set becomes too big (usually around 30 numbers), the time period the program takes to execute gets much larger, often way too large to be usable.

What would be an algorithm that cuts down on execution time, while achieving the same (or approximate) result?

EDIT: numbers are floats between 0 and 1.

Looking for a maximum average $m$ below a threshold $m_{max}$ is the same than looking for a maximum sum $s$ below a threshold $s_{max}$. If you have to select $k = 10$ numbers among $N$, you have:

$s_{max} = k \times m_{max}$

now the question looks like a Knapsack problem with a forced number of selected items $k$. You can use a DP solution closed to the one solving Knapsack. I also assume $s_{max} > 0$ and all available numbers are strictly positives. Note, that you may apply a simple offset on all numbers and $m_{max}$ if any is negative.

Let's build a $k\times s_{max}$ array $A$ with $A[i, j]$, the index of the last number selected to have $i$ selected values for a total of $j$. $A$ is initially filled with an "null" value.

Then the pseudo algorithm is:

for n from 1 to N:
    v = n-th available value
    for i from k-1 to 1:
        for j from smax-v to 1:
            if A[i, j] is not null and A[i+1, j+v] is null then:
                A[i+1, j+v] = n  
    if A[1, v] is null:
        A[1, v] = n

The best sum you can obtain is the last $A[k, j]$ which is not null. Using the index in $A$, you can backtrack the subset. Note that $i$ and $j$ loops go backward, to be sure the same value is not used twice.

Complexity is $O(Nks_{max})$ in time and $O(ks_{max})$ in space.

If $s_{max}$ is large and $N$ quite small, a (key, value) structure (in fact $k$ of these structures) instead of $A$ may be much more efficient as you won't have to loop on all empty values.

StackExchange Computer Science Q#110021, answer score: 2