摘要
背包问题是经典的NP-hard组合优化问题之一,在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。文中用动态规划方法解决0-1背包问题,通过在Matlab6.5环境下对其算法进行测试和与其他方法对比分析,表明应用该方法可节省大量的计算时间,因而具有更高运行效率。
The knapsack problem is a classic NP- hard problem in the combinational optimization. It is valuable in many fields such as resource assignment, investment, decision and loading design. This paper solved the 0 - 1 knapsack problem by DP algorithm , and test the algorithm in Matlab 6.5. The algorithm shows its superiority after comparing with other methods.
出处
《计算机技术与发展》
2006年第4期88-89,92,共3页
Computer Technology and Development
关键词
0-1背包问题
DP算法
分治法
递归法
NP难问题
MADAB
0 - 1 knapsack problem
DP algorithm
dividing - and - conquering
recursive algorithm ~ NP - hard problem
Matlab
