显示一个序列中和等于10的所有组合

这个题的扩展应用很多,虽然下面运算的复杂度很高,但是其思想非常巧妙,借助位运算实现了所有可能的组合,关键是该思想值得借鉴,在没有比较好的方法的情况下,我们就需要一个个来试,但是要一个不漏的把所有情况都考虑到一般的方法很麻烦

下面就详细介绍一下该算法的思想:

(1)首先根据序列的长度确定组合数,如长度为8则最大的组合只可能是8

(2)从1到1<<8中每一个数的等于1的位就代表一种组合,我们把这种组合对应的数相加,看其是否等于所求的值,如何是就输出对应位的值

该算法显然可以再进行优化,但是其依然很难在大数据面前有效

首先就是循环的次数上,如果序列的长度是n,则需要查找的次数为2n-1,指数倍的增加显然性能会指数倍的下降

如何降低查找的次数,可以对序列先排序,找出序列中最小的x个数使得他们的和是最小的不小于m的序列,这意味着组合数就由n变为了x,查找上限2x-1,上限找到后就找下限,我们从最大的开始相加,直到y个数使得他们是最大的不大于m位置,这意味着至少需要y位是1的二进制,那么下限就变成了2y-1了。这一点在和较大的情况下有作用,比如序列长度是100,每个数都是1,让你找和为100的序列,x=100,y=100,这表示最大的组合数是100,这些组合数对应的二进制数有100个是1,那就一种情况了,如何统计二进制数中1的个数,这个用位运算比较快,同时为了进一步提高效率,可以结合y的值,统计1和0的个数同时统计,当1的个数>y的时候就查看,当0的个数大于n-100时表示该组合不行,就换下一个。

 1 #include <iostream>
 2 #include <bitset>
 3 using namespace std;
 4 void main()
 5 {
 6     
 7     int arry[]={1,5,3,4,2,10,6,7},num=0;
 8     int n=sizeof(arry)/sizeof(int);
 9     bitset<32> x;//由于[]取数的是倒着来的,所以可以设成32位,前面的0位,完全不被取到。
10     for(int i=0;i<1<<n;++i)
11     {
12         x=i;
13         num=0;//记住这的清0.。这是这个程序唯一易错的地方。在多次循环都要用到同一个计数器的时候,一定要记得在开始的时候清0;
14         
15         for(int j=0;j<n;++j)
16         {
17             if(x[j])
18                 num+=arry[j];
19         }
20         if(num==10)
21         {
22             cout<<x<<endl;
23             for(int j=0;j<n;++j)
24                 if(x[j])
25                     cout<<arry[j]<<"  ";
26                 
27                 cout<<endl;
28                 
29         }
30     }
31     cout<<x<<endl;
32     
33 }
原文地址:https://www.cnblogs.com/GoAhead/p/2523741.html