【笔记】枚举
枚举的概念
枚举：逐个尝试所有可能的方案。
先把问题划分成一系列离散的状态，然后遍历这些状态来求解问题。
比如求3x+5y=10的正整数解有多少，把x∈[0，10]，y∈[0，10]逐个列举就能找到所有解。
枚举步骤
- 确定解的空间（几元？一维的还是二维的？）
- 确定空间边界（min，max，step）
- 估算时间复杂度（别超了）
- 如果步骤3的时间复杂度超了，那么想办法减少枚举空间、变换枚举顺序……
例题：百鸡百钱
百鸡百钱是我国古代数学家张丘建在《算经》一书中提出的数学问题：“鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？”
假设公鸡买了x，母鸡买了y，小鸡买了z。
列方程如下：
5 x + 3 y + 1 3 z = 100 x + y + z = 100 5x+3y+\frac{1}{3}z=100\\ x+y+z=100 5x+3y+31z=100x+y+z=100
方案1
枚举x，枚举y，枚举z，再加上两个上面的约束方程。
解空间是三维的。
方案二
枚举x，枚举y。z可以用上面的方程 z = 100 − x − y z=100-x-y z=100−x−y表示。
解空间是二维的。
方案三
枚举x。
y、z解二元一次方程组得到x的表达式。
y = 25 − 7 4 x z = 75 + 3 4 x y=25-\frac74x\\ z=75+\frac34x y=25−47xz=75+43x
例题
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
原文地址：https://blog.csdn.net/m0_73676887/article/details/142313583
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！