共查询到14条相似文献,搜索用时 156 毫秒
1.
孙红丽 《数字社区&智能家居》2008,3(9):1534-1535
背包问题是算法设计分析中的经典问题,本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析,给出具体算法设计和实现过程,并以具体实例详细描述不同方法求解问题解时算法基本思想,总结三种方法实现的优缺点并得出结论。 相似文献
2.
0-1背包问题是算法设计分析中的经典问题,本文主要通过对回溯法、动态规划、贪心算法和遗传算法的研究,分析这四种方法在求解0-1背包问题时的优缺点并进行了比较. 相似文献
3.
解0-1背包问题的二进制差异演化算法 总被引:4,自引:2,他引:2
针对传统差异演化算法(DE)无法求解采用二进制编码问题的缺点,通过采用新的变异方法,提出了一种用于求解0-1背包问题的二进制差异演化算法,阐明了该算法求解背包问题的具体实现过程.通过多个0-1背包问题的仿真试验,表明了该算法在求解0-1背包问题时不仅能达到最优解,而且收敛速度快,同时也验证了算法在解决二进制编码问题上的可行性和有效性. 相似文献
4.
曹周进 《数字社区&智能家居》2009,(12)
该文论述了算法学习中非常经典的0-1背包问题,探讨用穷举、搜索、动态规划三种算法来解决0-1背包问题,并讨论算法在时间和空间复杂度上的优化,给出具体的参考程序。 相似文献
5.
0/1背包问题是计算机科学中的一个经典问题。动态规划法,递归法,回溯法是求解该问题的三种典型方法,使用这三种方法求解0/1背包问题,并对各算法进行了理论分析。用不同规模的0/1背包问题对三种算法进行测试,比较它们的运行时间,发现测试结果与其理论分析结果相符.最后指出就求解不同规模的0/1背包问题而言各算法的优劣。 相似文献
6.
7.
8.
本文对“0/1背包问题”采用贪婪算法、动态规划、回溯法、分枝限界四种不同方法进行求解和算法分析,并通过各种算法的实现,研究了0/1背包问题的实质。 相似文献
9.
0/1背包问题是实际当中经常遇到的一类经典NP-hard组合优化问题之一。本文分别从贪心方法、动态规划、回溯法、分枝-限界法,遗传算法这五种算法设计方法入手,概述了各种设计方法的基本原理,提出了求解0/1背包问题的算法思想,并对算法进行分析,提出了改进方法。 相似文献
10.
0-1背包问题是计算机科学中一个经典问题,0-1背包问题是一个最优化问题。因其结构简单,可扩展性强,可作为其他问题的子问题,因此通过对其研究可以解决更为复杂的优化问题。本文概述了两种求解0-1背包问题的算法设计方法,并对两种算法进行了分析和比较。 相似文献
11.
0/1背包问题是实际当中经常遇到的一类经典NP—hard组合优化问题之一。本文分别从贪心方法、动态规划、回溯法、分枝-限界法.遗传算法这五种算法设计方法入手,概述了各种设计方法的基本原理,提出了求解0/1背包问题的算法思想,并对算法进行分析.提出了改进方法。 相似文献
12.
基于动态状态树的回溯算法 总被引:1,自引:0,他引:1
介绍了背包问题及0-1背包问题,阐述了回溯算法(算法设计的基本方法之一)和状态空间的概念,提出一个基于动态状态空间树的回溯算法.以0-1背包问题为例,说明动态树方法对求解线性规划问题等是非常有用的,且该算法所用时间少于静态状态空间树方法,有助于扩大回溯算法的应用. 相似文献
13.
背包问题是经典的NP-hard组合优化问题之一,在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。文中用动态规划方法解决0-1背包问题,通过在Matlab6.5环境下对其算法进行测试和与其他方法对比分析,表明应用该方法可节省大量的计算时间,因而具有更高运行效率。 相似文献
14.
本文对“0/1背包问题”采用贪婪算法、动态规划、回溯法、分枝限界四种不同方法进行求解和算法分析.并通过各种算法的实现.研究了0/1背包问题的实质。 相似文献