皇后问题研究及算法比较分析田金梁.docx

《算法分析与设计》课程大作业目背包问题研究及算法分析 0-1 题—计算机与信息工程学院别院—专业计算机与科学技术—2013 年级级1308114091学号 田金梁名姓—王鲜芳 指导教师 绩成 11/19/2019背包问题研究及算法分析0-1摘要背包问题是一个在运筹学领域里常见的典型NP-C难题,也是算法设计分析中的经典问题,对该问题的求解方法的研究无论是在理论上 ,还是在实践中都具有重要意义。对这个问题的求解已经研究出了不少的经典方法,对该问题的探索和应用研究一直在进行。在先进理论指导下,求解0-1背包问题具有科学、高效、经济、灵活、方便等显著特点。那么要解决背包问题,首要的前提就是设计出好的算法,想求得背包问题的解,就要先设计出算法,本文采用回溯法对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析,给出具体算法设计和实现过程。并以具体实例详细描述不同方法求解问题解时算法基本思想,然后就解决0-1背包问题对这四种算法进行详细的比较,总结这种方法实现的优缺点并得出结论。如何将背包问题应用于实际问题中,有针对性地设计适合求解实际0-1背包问题的算法,并很好地解决实际问题,是计算机工作者不断思索、研究的一个领域。关键词背包问题算法分析回溯法时间复杂度Researchandalgorithmanalysisof0-1knapsackproblemAbstractKnapsackproblemisainoperationsresearchinthefieldoftypicalNP-Cproblem,isthedesignandanalysisofalgorithmsintheclassicproblem,,,solving0-1knapsackproblemhassignificantcharacteristicsofscientificandefficient,economic,flexible,,thefirstpremiseistodesignagoodalgorithm,toobtainthesolutionoftheknapsackproblem,wemustfirstdesignalgorithm,plexityanalysisofthealgorithmdesignand-01knapsackproblemandthesimple-01knapsackproblem,,andthensolvethe0-parisonofthefouralgorithms,,todesignsuitableforsolving0-1knapsackproblemthealgorithm,anditisquitegoodtosolvepracticalproblems,puterworkers, 2一、绪论 5问题的研究及意义 51背包问题的算法研究与分析 5课题的主要研究内容 5、0- 61背包问题的实现 6三、0-1背包问题在分枝-限界法中的实现 8分枝-限界法的基本原理与分析 81背包问题的实现 810121618四、0-1背包问题在遗传算法中的实现 遗传算法的基本原理与分析 101背包问题的实现 11五、0-1背包问题在回溯法中的实现 回溯法的基本原理与分析 121背包问题的实现 -1背包问题在回溯法中的算法描述 13算法效率 15六、四种算法的比较与分析