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

发布时间：2020-12-13 17:55:35 所属栏目：PHP教程来源：网络整理

导读：特定一组数字n [1],n [2],n [3],…… n [x] 还有一个数字M. 我想找到最好的组合 n[a] + n[b] + n[c] + ... + n[?] = M 组合应该达到达到或超过M所需的最小值,没有其他组合可以获得更好的结果. 将在PHP中执行此操作,因此可以使用PHP库.如果没有,只需一般算法

特定
一组数字n [1],n [2],n [3],…… n [x]
还有一个数字M.

我想找到最好的组合

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

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

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!