6升小米6——算法解题

　　今天好兄弟说要买小米6，让我帮忙写个小程序在16个数中找出6个相加和为6666的数。

作为一个有素养的算法工程师，第一想到的自然是夹逼，不过6个数的夹逼有些难写。

看了看题目，觉得脑算也不过1分钟啊，明显3个最大的都要选，剩483，选两个尾数是9，一个位数是5的，试着选125和75，最后得出 1956 75 159 249 2099 2128，算法也不过深搜加剪枝，（半年没写算法了），夹逼的话，速度肯定要快，不过算法设计比较难，考虑这个深搜的话解空间不会很庞大，（按时交付才是最重要的，有时间在开发v2.0嘛，敏捷开发嘛）

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 
 7 bool fin(vector<int> num,int n,int i){
 8     if( i!=num.size()){
 9         num.erase(num.begin()+i);
10     }
11     for(int it=0;it!=num.size();++it){
12         if(n-num[it]==0){   //成功返回
13             cout<<num[it]<<" ";
14             return true;
15         }
16         if(n-num[it]<0){    //小于0剪枝
17             return false;
18         }
19         if(fin(num,n-num[it],it)){  //递归求解
20             cout<<num[it]<<" ";
21             return true;
22         }
23     }
24     return false;
25 }
26 
27 int main()
28 {
29     vector<int> num(16);
30     for(int i=0;i!=16;i++){
31         cin>>num[i];
32     }
33     sort(num.begin(),num.end());
34     reverse(num.begin(),num.end());
35 
36     if(fin(num,6666,16))
37         return 0;
38 
39 
40     return 0;
41 }
42 //19 29 39 75 89 89 89 125 129 159 236 249 299 1956 2099 2128

速度没看，不过16个数，很快。

6升小米6——算法解题

推荐阅读