枚举算法

吾生也有涯，而知也无涯。——庄子

介绍

枚举法，也称为穷尽法，指的是从问题所有可能的解的集合中一一枚举各元素。用题目中给定的检验条件判定哪些是有用的，哪些是无用的。能使命题成立，即为其解。

• 优点是算法简单，在局部地方使用枚举法，效果十分好。
• 缺点是运算量过大，当问题的规模变大的时候，循环的阶数越大，执行速度越慢。
• 能不用枚举就不用枚举！即使使用枚举也要尽量优化！

例题

百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，公鸡一只3元，母鸡一只5元，小鸡三只1元，试求100元买100只鸡，各为多少才合适？

解析

• 根据题意，我们可以得到方程组：

$\begin{cases} 3x+5y+z/3 = 100\\ x+y+z = 100\\ \end{cases},(100 \geq x,y,z \geq 0,z \% 3 == 0)$

• 代码示例1

if __name__ == '__main__':
    for x in range(101):
        for y in range(101):
            for z in range(101):
                if x + y + z == 100 and 3 * x + 5 * y + z / 3 == 100 and z % 3 == 0:
                    print(x, y, z)

• 根据已知条件，进行代码优化，减少枚举次数
  三种鸡的和是固定的，我们只要枚举x,y，第三种鸡就可以根据约束条件求得z = 100 - x - y,这样就缩小了枚举范围。

$\begin{cases} 4x+7y = 100\\ x+y+z = 100\\ \end{cases},(0 \leq x \leq 25,y \% 7 ==0,y \geq 0,z \% 3 == 0)$

• 代码示例2

if __name__ == '__main__':
   for x in range(26):
       y = 100 - 4 * x
       if y % 7 == 0 and y >= 0:
           y /= 7
           z = 100 - x - y
           if 4 * x + 7 * y == 100 and z % 3 == 0:
               print(x, y, z)