| 摘要: |
| 在分析早期邮票问题算法思路的基础上,提出静态搜索限制规划、可变上界式动态搜索限制规划和可变上、下界式动态搜索限制规划对早期邮票问题算法进行优化.优化后的算法在h=3,n=9时计算邮票问题的大概时间分别为13h,6min,11s.动态搜索限制规划优化后的算法大大缩短了邮票问题的计算时间,算法效率明显提升. |
| 关键词: 动态规划 剪枝 可变下界 NP问题 |
| DOI： |
| 投稿时间：2008-02-25修订日期：2008-04-05 |
| 基金项目: |
|
| The Optimization of the Algorithm on Postage Stamps Problem |
|
PENG Lin-hao
|
| (No.2 Middle School of Nanning, Nanning, Guangxi, 530012, China) |
| Abstract: |
| Based on the analysis of early development problem in Stamps, this article proposed the optimizing algorithm by using static programming, dynamic programming with maximum value limitation only, and dynamic programming with minimum and maximum limitation.When h=3,n=9, the time for the calculation decreased to 11h 6min and 11s.The optimized dynamic programming significantly increased the efficiency of the algorithm. |
| Key words: dynamic programming pruning changeable limitation of minimum no-polynomial problem |
