科研之友
微信
新浪微博
Facebook
分享链接
摘要
对于具有NP难度的完全0-1背包问题，本文提出了一种基于贪心与回溯思想的局部动态规划算法。该算法借鉴贪心与回溯技术快速找到近似最优解，再通过局部动态规划的结果回溯逼近最优解，兼顾了算法的正确性与时间复杂度。相比于传统动态规划算法，该算法在大多数情况下能够显著缩短求解时间；而相较于智能算法，该算法能够保证所求解是最优解。大量的实验结果表明，本文所提出的算法在绝大多数情形下均能够在更短时间内准确找到问题的最优解；并且该算法贪心地进行最大单位平均价值成分的选取，背包容量不再直接影响求解时间，因此对于背包容量极大的情况，该算法能够极大地缩短求解时间。
- 单位
