算法分析与设计大作业实验题目: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 背包问题得
