背包问题求解方法综述.pdf

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