二进制枚举算法

二进制&＃xff1a;是计算技术中广泛采用的一种数制。二进制数据是用0和1两个数码来表示的数。它的基数为2&＃xff0c;进位规则是“逢二进一”&＃xff0c;借位规则是“借一当二”
子集&＃xff1a;是一个数学概念&＃xff1a;如果集合A的任意一个元素都是集合B的元素&＃xff0c;那么集合A称为集合B的子集。
含有N个元素的集合的一切子集的个数为 2^n。简单证明一下&＃xff1a;
含有0个元素的子集有C(N,0)个&＃xff0c;
含有1个元素的子集有C(N,1)个&＃xff0c;
含有2个元素的子集有C(N,2)个&＃xff0c;
…
含有N个元素的子集有C(N,N)个
由二项式系数的性质可得&＃xff1a;C(N,0)&＃43;C(N,1)&＃43;C(N,2)&＃43;…&＃43;C(N,N)&＃61;2^n。

1. 自学二进制枚举后自己理解

根据我自己的理解来说二进制枚举就是通过二进制只有0和1两个数值来表示其代表的值是否被我们选中。
所解决的问题&＃xff1a;他所解决的问题就是已经告诉我们一个固定数量的值或数&＃xff0c;并让我们来计算我们能有多少种不同的选择结果。

首先我吗来补充一波知识
按位与运算&＃xff08;&&＃xff09;
A&B&＃xff08;A&＃xff0c;B表示十进制数&＃xff09;表示将A&＃xff0c;B转换成十进制数进行比较&＃xff0c;如&＃xff1a;1&0&＃61;0&＃xff1b;1&1&＃61;1&＃xff1b;0&0&＃61;0&＃xff1b;3&5&＃61;011&101&＃61;001&＃xff1b;

移位运算符&＃xff08;<<&＃xff09;
A< 通常认为A<

接下来我们就来看一题题目来实战一下吧
锐锐有一个神奇的口袋&＃xff0c;总的容积是40&＃xff0c;用这个口袋可以变出一些物品&＃xff0c;这些物品的总体积必须是40。锐锐现在有n个想要得到的物品&＃xff0c;每个物品的体积分别是a1&＃xff0c;a2……an。锐锐可以从这些物品中选择一些&＃xff0c;如果选出的物体的总体积是40&＃xff0c;那么利用这个神奇的口袋&＃xff0c;锐锐就可以得到这些物品。现在的问题是&＃xff0c;锐锐有多少种不同的选择物品的方式。
输入格式&＃xff1a;输入的第一行是正整数n (1 <&＃61; n <&＃61; 20)&＃xff0c;表示不同的物品的数目。接下来的n行&＃xff0c;每行有一个1到40之间的正整数&＃xff0c;分别给出a1&＃xff0c;a2……an的值。
输出格式&＃xff1a;输出不同的选择物品的方式的数目。
分析&＃xff1a;假设输入为
3
20
20
20
那么那么我们就可以很容易的知道这最终输出的结果为3&＃xff0c;因为a1,a2,a3都为20
那么此时因为有3个数那么用三位二进制数就可以表示相应的a1,a2,a3是否被选中。

因为这三个数据每个都有0或1两种状态&＃xff0c;因此他就有7种转态来表示其不同的选择情况分别为&＃xff1a;
a1 a2 a3
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
因此代码为&＃xff1a;

#include
#include
using namespace std;
int main(){int number,arg[20],nu&＃61;0,sum;scanf("%d",&number);for(int i &＃61;0;i<number;i&＃43;&＃43;) scanf("%d",&arg[i]);//输入每个数值for(int i &＃61; 0;i<(1<<number);i&＃43;&＃43;){//1<sum &＃61; 0;for(int j &＃61; 0;j<number;j&＃43;&＃43;)if(i&(1<<j)) sum &＃61; sum &＃43;arg[j];//这里i&&＃xff08;1<if(sum&＃61;&＃61;40) nu&＃43;&＃43;;}cout<<nu<<endl;return 0;}


新人第一次写博客&＃xff0c;如果有什么错误或不足的地方希望大家指正