0-1背包问题 动态规划和回溯法的比较 |
| |
引用本文: | 丁战.0-1背包问题 动态规划和回溯法的比较[J].程序员,2004(7):92-94. |
| |
作者姓名: | 丁战 |
| |
摘 要: | 动态规划算法是特待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解.而田溯法是从开始结点(根结点)出发,以深度优先的方式搜索整个解空间.获取于0-1背包问题的最优解通常有动态规划算法和回溯法,本文着力比较这两种算法的复杂度和适用场合。
|
关 键 词: | 回溯法 背包问题 搜索 动态规划算法 深度优先 结点 复杂度 方式 适用 获取 |
本文献已被 维普 等数据库收录! |
|