特定
一组数字n [1],n [2],n [3],…… n [x]
还有一个数字M.
一组数字n [1],n [2],n [3],…… n [x]
还有一个数字M.
我想找到最好的组合
n[a] + n[b] + n[c] + ... + n[?] >= M
组合应该达到达到或超过M所需的最小值,没有其他组合可以获得更好的结果.
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
