想要使用枚举算法,首先要确定枚举对象、枚举范围和判定条件。逐一枚举可能的解,验证每个解是否是问题的解,千万不要漏掉任何一个可能正确的解。
举个栗子
百钱买百鸡问题:有一个人有一百块钱,打算买一百只鸡。到市场一看,大鸡三块钱一只,小鸡一块钱三只,不大不小的鸡两块钱一只。现在,请你编一程序,帮他计划一下,怎么样买法,才能刚好用一百块钱买一百只鸡?
我们可以设公鸡为x,母鸡为y,小鸡为z,可以得出下列方程:
x + y +z=100;
5x + 3y + z/3 = 100; 现在只要穷举每一个 公鸡的值,母鸡,小鸡的值 就能通过公鸡的 x 表示出来。
代码:
图中代码使用了三次for循环 时间复杂度(不知道的不用担心后期会专门出文章来讨论) 为O(N^3); 我们都喜欢一个程序简便,不消耗空间,短小精悍,看着高端的那种。下面介绍优化。
优化套路
虽然枚举是一种很暴利的算法,但是仍可以通过缩小枚举范围来提高解决问题的效率。同时也要避免重复枚举。
来看第二种方式:
x+y+z = 100 ①
5x+3y+z/3 = 100 ②
令②x3-① 可得
7x+4y = 100
=>y = 25-(7/4)x ③
又因为0 < y < 100 的自然数,则可令
x = 4k ④
将④代入③可得
=> y = 25-7k ⑤
将④⑤代入①可知
=> z = 75+3k ⑥
要保证 0 < x,y,z < 100 的话,k的取值范围只能是1,2,3
代码:
这个代码就达到了一层循环的基础,时间复杂度为 O(n);
这个栗子介绍了枚举优化的一种套路就是减少枚举的变量。整个优化枚举的套路主要是有两个方面一个是减少枚举变量,一个是缩小枚举范围。
以上就是Java枚举的使用方式和算法介绍的详细内容,更多请关注php中文网其它相关文章!