背包问题求解方法综述(共27页).doc

精选优质文档-倾情为你奉上算法分析与设计大作业实验题目：0-1背包问题求解方法综述组 员： 班级：指导老师：0-1背包问题求解方法综述【摘要】：0-1背包问题是一个经典的NP-hard组合优化问题，现实生活中的很多问题都可以以它为模型。本文首先对背包问题做了阐述，然后用蛮力解法、动态规划算法、贪心算法和回溯解法对背包问题进行求解，分析了0-1背包问题的数学模型,刻划了最优解的结构特征,建立了求最优值的递归关系式。最后对四种算法从不同角度进行了对比和总结。【关键词】：0-1背包问题；蛮力解法；动态规划算法；贪心算法；回溯解法。0.引言0-1背包问题是指给定n个物品,每个物品均有自己的价值vi和重量wi(i=1,2,n),再给定一个背包,其容量为W。要求从n个物品中选出一部分物品装入背包,这部分物品的重量之和不超过背包的容量,且价值之和最大。单个物品要么装入,要么不装入。很多问题都可以抽象成该问题模型,如配载问题、物资调运