算法来选择一组数字达到最小总 [英] Algorithm to select a set of numbers to reach a minimum total

问题描述

由于 一组数字 N [1]，N [2]，N [3]，... N [X] 而一个数M

我想找到的最佳组合

  N [A] + N [B] + N [C] + ... + N＆GT [？] = M
 

组合应达到达到或超越米，没有其他的组合给人一种更好的成绩的最低要求。

都用PHP这样做使PHP库的使用就可以了。如果没有，只是一般的算法就可以了。谢谢！

解决方案

 伪code：

名单＆LT;集＆gt;结果;
INT米;
名单＆LT;诠释＆GT;一个;

// ...

a.sort（）;

对于每个i在[0..a.size]
    F（I，EMPTY_SET）;

// ...

无效F（INT IND，设置current_set）
{
    current_set.add（一个[IND]）;

    如果（current_set.sum＆GT;米）
    {
        results.add（current_set）;
    }
    其他
    {
        的for（int i = IND + 1; I＆LT; a.size ++ I）
        {
            F（I，current_set）; //传值设置

            //如果previous呼叫到达的解决方案，没有必要继续
            如果（A [IND] + current_set.sum）＆GT;米
                打破;
        }
    }
}

//选择任何最佳的结果你需要的结果，一个
//用最低的金额或最低数目的元素
 

Given A set of numbers n[1], n[2], n[3], .... n[x] And a number M

I would like to find the best combination of

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

The combination should reach the minimum required to reach or go beyond M with no other combination giving a better result.

Will be doing this in PHP so usage of PHP libraries is ok. If not, just a general algorithm will do. Thanks!

解决方案

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

这篇关于算法来选择一组数字达到最小总的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！