【笔记】枚举

枚举的概念

枚举：逐个尝试所有可能的方案。

先把问题划分成一系列离散的状态，然后遍历这些状态来求解问题。

比如求3x+5y=10的正整数解有多少，把x∈[0，10]，y∈[0，10]逐个列举就能找到所有解。

枚举步骤

1. 确定解的空间（几元？一维的还是二维的？）
2. 确定空间边界（min，max，step）
3. 估算时间复杂度（别超了）
4. 如果步骤3的时间复杂度超了，那么想办法减少枚举空间、变换枚举顺序……

例题：百鸡百钱

百鸡百钱是我国古代数学家张丘建在《算经》一书中提出的数学问题：“鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？”

假设公鸡买了x，母鸡买了y，小鸡买了z。

列方程如下：

$$\begin{gathered} 5x+3y+\frac{1}{3}z=100 \\ x+y+z=100 \end{gathered}$$

方案1

枚举x，枚举y，枚举z，再加上两个上面的约束方程。

解空间是三维的。

方案二

枚举x，枚举y。z可以用上面的方程$z=100-x-y$表示。

解空间是二维的。

方案三

枚举x。

y、z解二元一次方程组得到x的表达式。

$$\begin{gathered} y=25-\frac{7}{4}x \\ z=75+\frac{3}{4}x \end{gathered}$$

例题

https://blog.csdn.net/m0_73676887/article/details/142313916
https://blog.csdn.net/m0_73676887/article/details/142313873
https://blog.csdn.net/m0_73676887/article/details/142313818
https://blog.csdn.net/m0_73676887/article/details/142313775