|
本帖最后由 老陈 于 2012-12-25 04:59 编辑
我说一下这道题我的解题思路。
我是用计算机编程序解的,在出题时我高估计算机CPU的计算能力,也就是低估题目的计算复杂性。因此在原题目中写了N是一个很大的数。实际计算中当N=2000时就很难计算出最优解了。
我是采用逼近的算法解的。
以N=1000,4种筹码为例。
首先给4种筹码一个初始值:比如(1,5,25,125)
用符合逻辑的初始值就可以,结果与初始值无关,只是稍微影响找到最佳方案的更速度。
1是必须的。
然后在初始值“附近”搜索更好的方案。
“附近”的意思:
5附近为3-8
25附近为18-33
125附近为93-154
这个“附近”不能太大(会使计算复杂),也不能太小(会丢掉更好的方案)。
进行三重循环搜索更好的方案。当找到更好的方案后再在更好的方案“附近”搜索更好的方案。
一直到找不到更好的方案为止。
4种筹码策略用三重循环,5种筹码策略用四重循环,程序是用递归的方法写的,适用于多种筹码策略。
搜索方案也是用递归的方法写的。
Search(CHips,NC)
CHips是筹码数,NC是筹码种类
在使用了1个125的筹码后就
Search(875,3)
当搜索到Search(X,1)就结束了,用X个1$筹码就可以了。把筹码总和记住。所有可能的组合找出筹码最少的。
CHips从1到N搜索,把各个筹码总和加起来,与前一个方案比较,如果这个方案好就在这个方案搜索,否则计算其它方案。
我的计算结果是:
100(1,12,19)=1563
500(1,13,69)=14982
500(1,7,56,95)=13648
500(1,7,17,72,118)=13705
1000(1,18,97)=38955
1000(1,9,89,140)=33996
1000(1,7,52,137,218)=33335
2000(1,22,162)=100488
2000(1,12,138,236)=83884
5000(1,29,300)=349944
10000(1,38,469)=894672
第一个数字为N
括号里的数字个数为筹码种类,单个数字为筹码面值
最后一个数为所有表达1到N的筹码总和乘以筹码种类
N越大,筹码种类越多计算就越复杂。
N=2000的5种筹码就很难算了,我编的程序只少需要12个小时。
|
|