算法分析与设计大作业实验题目:01 背包问题求解方法综述组 员: 班 级:指导老师:01 背包问题求解方法综述【摘要】:01 背包问题就是一个经典得 NPhard 组合优化问题,现实生活中得很多问题都可以以它为模型。本文首先对背包问题做了阐述,然后用蛮力解法、动态规划算法、贪心算法与回溯解法对背包问题进行求解,分析了 01 背包问题得数学模型,刻划了最优解得结构特征,建立了求最优值得递归关系式。最后对四种算法从不同角度进行了对比与总结。【关键词】:01 背包问题;蛮力解法;动态规划算法;贪心算法;回溯解法。0、引言01 背 包 问 题 就 是 指 给 定 n 个 物 品 , 每 个 物 品 均 有 自 己 得 价 值 vi 与 重 量wi(i=1,2,…,n),再给定一个背包,其容量为 W。要求从 n 个物品中选出一部分物品装入背包,这部分物品得重量之与不超过背包得容量,且价值之与最大。单个物品要么装入,要么不装入。很多问题都可以抽象成该问题模型,如配载问题、物资调运[1]问题等,因此讨论该问题具有较高得实际应用价值。目前,解决 01背包问题得方法有很多,主要有动态规划法、回溯法、分支限界法、遗传算法、粒子群算法、人工鱼群算法、蚁群算法、模拟退火算法、蜂群算法、禁忌搜索算法等。其中动态规划、回溯法、分支限界法时间复杂性比较高,计算智能算法可能出现局部收敛,不一定能找出问题得最优解。文中在动态规划法得基础上进行了改进,提出一种求解 01 背包问题得算法,该算法每一次执行总能得到问题得最优解,就是确定性算法,算法得时间复杂性最坏可能为 O(2n)。1、01 背包问题描述01 背包问题(KP01)就是一个著名得组合优化问题。它应用在许多实际领域,如项目选择、资源分布、投资决策等。背包问题得名于如何选择最合适得物品放置于给定背包中。本文主要讨论背包问题中最基础得 0/1 背包问题得一些解决方法。为解决背包问题,大量学者在过去得几十年中提出了很多解决方法。解决背包问题得算法有最优算法与启发式算法[2],最优算法包括穷举法、动态规划法、分支定界法、图论法等,启发式算法包括贪心算法、遗传算法、蚁群算法、粒子算法等一些智能算法。01 背包问题一般描述为:给定 n 种物品与一个背包。物品 i 得重量就是w(i),其价值为 v(i),背包得容量为 c。问应该如何选择装入背包得物品,使得装入背包中得物品得总价值最大？在选择装入背包得物品时,对每种物品 i 只有两种选择,即装入背包或不装入背包。不能将物...
