-
题名0/1背包问题的c++实现
- 1
-
-
作者
贺晓伟
-
机构
中国地质大学
-
出处
《数字技术与应用》
2011年第8期150-150,152,共2页
-
文摘
0/1背包问题是计算机科学中的一个经典问题。实际问题中我们经常需要解决最优化问题,即研究如何在限制条件下,求出优化函数的最优值。贪婪算法是解决此类问题的一种直观的求解方法。因为所求问题的最优解可以通过一系列局部最优的选择完成,或者反过来说,一个问题的最优解包含了其子问题的最优解。因此此类具有最优子结构性质的问题可以用贪婪算法。其主要思想为:求解过程中,采用逐步构造最优解的方法,在每个阶段,都做出一个看上去最优的决策(按照一定标准即贪婪准则)。决策一旦作出,就不可再更改。
-
关键词
0/1背包问题
贪婪算法
贪婪准则
C++
-
Keywords
the 0/1 knapsack problem greedy algorithm greedy criterion C＋＋
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
-
题名基于0/1背包问题的讨论
- 2
-
-
作者
林鑫
-
机构
同济大学计算机系
-
出处
《微型电脑应用》
2007年第4期15-16,32,共3页
-
文摘
简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(SAA),并使用这三种算法解决了0/1背包问题,给出了具体的算法描述和求解过程。对三种方法解决此问题,进行了仿真模拟和算法分析,指出了在不同规模下各种方法的优缺点,最后分析了解的质量和CPU时间。
-
关键词
0/I背包问题
贪婪算法
启发式贪婪算法
模拟退火算法
CPU时间
-
Keywords
0/1 knapsack problem greedy algorithm Heuristic greedy algorithm Simulated annealing algorithm (SAA) CPU time
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
