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

前端之家收集整理的这篇文章主要介绍了php – 选择一组数字以达到最小总数的算法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
特定
一组数字n [1],n [2],n [3],…… n [x]
还有一个数字M.

我想找到最好的组合

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

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

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

  1. pseudocode:
  2.  
  3. list<set> results;
  4. int m;
  5. list<int> a;
  6.  
  7. // ...
  8.  
  9. a.sort();
  10.  
  11. for each i in [0..a.size]
  12. f(i,empty_set);
  13.  
  14. // ...
  15.  
  16. void f(int ind,set current_set)
  17. {
  18. current_set.add(a[ind]);
  19.  
  20. if (current_set.sum > m)
  21. {
  22. results.add(current_set);
  23. }
  24. else
  25. {
  26. for (int i=ind + 1; i<a.size; ++i)
  27. {
  28. f(i,current_set); // pass set by value
  29.  
  30. // if prevIoUs call reached solution,no need to continue
  31. if (a[ind] + current_set.sum) > m
  32. break;
  33. }
  34. }
  35. }
  36.  
  37. // choose whatever "best" result you need from results,the one
  38. // with the lowest sum or lowest number of elements

猜你在找的PHP相关文章