贪心算法的介绍+枚举算法的介绍（brute force）：包含练手题目_贪心算法和枚举算法的区别

一、什么是贪心算法

贪心值每一步都做出当前最优的选择。一般解决的问题有如下特点：局部最优能导致全局最优。

1. 举个例子：

问题如下：
纸币面额有1元、2元、10元、100元。问凑出正好x元最少要多少张纸币？
1
2

关键思路：我们就可以用贪心，每一次都尽量取面额大的，不断凑出x；
为什么这样贪心不会有问题？
因为 1 2 10 100， 这些数字之间，他们有整除关系，这意味着，多张小面额的纸币，一定可以被面额大的数字所代替；
如果现在的纸币面额为1 15 17 21，那么还可以用贪心吗？思考一下；
现在已经不存在整除关系了，那么大面额的纸币也没有办法被多张小面额的纸币代替（这里不是说的1元的纸币），举个例子看看：
比如：32 按照贪心的思路，就应该是，21 （1张）+ 1 （11张），这样就很多了，但是我们要是直接去15 和 17，一下就可以凑出32元了，所以这里贪心就不对了，做不到由局部的最优解导致全局最优；

2. 在贪心中排序和优先队列会用的比较多（抓住这两个重点），在这里过一下sort的知识点

（1）sort

int nums[1005]; // 数组
填充数组数据有 n 个
sort(nums, nums + n); //排序从0 - n - 1，默认按照从小到大排序

- 那么想从小到大排序呢？
- 写一个bool cmp() 函数  cmp：这个函数名字无所谓的，想叫什么叫什么
- 举例如下：
// 我这里是对int型数据进行排序的
bool cmp(int x, int y) {
	return x > y; // x真大于y，为true，就排在前面，也就是大的数字排在了前面，从大到小排序 （我是这么记忆的）
}

sort (nums, nums + n, cmp);
1
2
3
4
5
6
7
8
9
10
11
12
13

（2）关于优先队列，我写过一篇关于stl的粗略实操，可以过一下，或者上网找教程看一下

STL 相关知识点粗略浅过一下（包括迭代器）

二、枚举的介绍（两种：朴素和状压）

1. 朴素枚举

顾名思义，用for循环枚举所有的情况。
《算术教室》
这一题，如果用O（n^2）的时间复杂度来枚举，可以通过n <= 3000的数据（一般时间限制是1s）。但是对于n<=100000肯定会超时

2. 状压枚举：所有的状压枚举都是可以用dfs（深度优先搜索）来写的，但是状压枚举写不了dfs：

（1）适合场景

共有n个物品，每个物品有m中状态，枚举所有物品的所有状态，复杂度为O（m^n）；
借助n进制的性质进行枚举；

（2）二进制状压枚举的写法：

n超过20就不建议写暴力枚举；

典型场景：
总共有n个数：a1、a2、…an，每个数可以取也可以不取，枚举所有方案；
状压：每个数字取就代表1，不取代表0，二进制
所有数字都不取就是00000000，转换成10进制为0；
所有数字都取就是11111111，转换成10进制为2^n - 1（2的n次方 - 1）；二进制的状态；
那就可以通过一个数i，枚举从0到2^n - 1，i是一个十进制，通过其二进制的表达就可以知道它每一位是取还是不取

模板
二进制
for (int i = 0; i < 1 << n; ++i) { // i为从1到2^n的状态压缩值 2^n
	int p = i; // 先将i取出
	int sum = 0； // 用一个变量来维护取出的数之和
	for (int j = 0; j < n; ++j) {//转为二进制进行操作
		sum += p % 2 * a[i]; // 求取出来的数之和，p % 2为对应的二进制位 （&1）
		// 中间可以进行其他的操作
		p /= 2; // 求下一个二进制位，或者p >> 1右移一位
	}
	// 这里可以添加想要的操作
}

三进制同理，添加一步预处理操作，把3^n打完表
1
2
3
4
5
6
7
8
9
10
11
12
13
14

m个状态就可以转换成m进制的n位数；
00000… ~ (m-1)(m-1)(m-1)(m-1)(m-1)…
m^n个数
步骤：先把m^n个数，都遍历，转换成m进制，一个一个求每一位，就知道每个情况的每一位的状态；
写n个for循环不现实；

三、对于贪心和枚举的练手题，会单独再整理出来

• 疯狂的自我检索者（贪心）
• chika和蜜柑（贪心/优先队列）
• you和帆船（枚举）
• 数位染色（状压枚举/dfs）
• ranko的手表（枚举）