选择一组数字以达到最小总数的算法

Question

给出一组数字n[1], n[2], n[3], .... n[x] 和一个数字M.

我想找到最好的组合

n[a] + n[b] + n[c] + ... + n[?] >= M

组合应该达到达到或超过M所需的最小值,没有其他组合可以获得更好的结果.

将在PHP中执行此操作,因此可以使用PHP库.如果没有,只需一般算法即可.谢谢!

Answer 1

pseudocode:

list<set> results;
int m;
list<int> a;

// ...    

a.sort();

for each i in [0..a.size]
    f(i, empty_set);    

// ...

void f(int ind, set current_set)
{
    current_set.add(a[ind]);

    if (current_set.sum > m)
    {
        results.add(current_set);
    }
    else
    {
        for (int i=ind + 1; i<a.size; ++i)
        {
            f(i, current_set);  // pass set by value

            // if previous call reached solution, no need to continue
            if (a[ind] + current_set.sum) > m
                break;
        }
    }
}

// choose whatever "best" result you need from results, the one
// with the lowest sum or lowest number of elements