特定
一组数字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