背包问题(1)_精品文档.docVIP

背包问题报告

小组成员：张灿、吴雪涛、高坤、占强、习慧平

小组分工情况

小组成员

查找资料

制作ppt

编写程序

讲解ppt

制作报告

张灿

ⅴ

ⅴ

ⅴ

ⅴ

ⅴ

吴雪涛

ⅴ

高坤

ⅴ

ⅴ

占强

ⅴ

习慧平

ⅴ

背包问题

背包问题的历史由来

它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是必威体育官网网址的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。在解决大量的复杂组合优化问题时，它常常作为一个子问题出现，从实际的观点看，许多问题可以用背包问题来描述，如装箱问题，货仓装载，预算控制，存储分配，项目选择决策等，都是典型的应用例子。随着网络技术的不断发展，背包公钥密码在电子商务中的公钥设计中也起着重要的作用。然而当问题的规模较大时，得到最优解是极其困难的。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。

背包问题的描述

背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？

背包问题的定义

我们有n种物品，物品j的重量为wj，价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。可以用公式表示为：

maximize

subjectto

如果限定物品j最多只能选择bj个，则问题称为有界背包问题。可以用公式表示为：

maximize

subjectto

如果不限定每种物品的数量，则问题称为无界背包问题。

背包问题的研究现状

Dantzing在20世纪50年代首先进行了开创性的研究，利用贪婪算法求得了0-1背包问题最优解的上界。1974年，horowitz和salmi利用分支限界法解答背包问题，并提出了背包问题的可分性，指出了求解该问题的一条新途径。随后，balas和zemel提出了背包问题的“核”思想，使背包问题的研究获得了较大进展。上世纪九十年代以后，随着生物仿生技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现，例如遗传算法己经在0/1背包问题上得到较好的应用，蚂蚁算法、粒子群算法等仿生算法也在组合优化问题

中得到了很好的应用。

求解0-1背包问题常见方法

传统求解该问题的方法可以概括为精确算法和近似算法，其中精确算法有动态规划法、回溯法、分支限界法等，近似算法有遗传算法、贪婪法、粒子群算法、蚁群算法等,由于精确算法的时间复杂性和空间复杂性等缺点，近年来利用近似算法求解背包问题成为重点。

5.1精确算法

5.1.1回溯法

回溯法的基本思想是在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发有哪些信誉好的足球投注网站解空间树，其用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被有哪些信誉好的足球投注网站遍才结束。用回溯法求解0-1背包问题是按照物品的单位价值从大到小排序,计算当前节点的上界,有哪些信誉好的足球投注网站左子树。只有当右子树包含可行解时才有哪些信誉好的足球投注网站右子树。剪去右子树的条件是当前价值加上剩余物品的总价值小于当前的最优总价值时,不需有哪些信誉好的足球投注网站右子树,可将右子树剪去。回溯法用一定的剪枝进行优化,算法的时间复杂度为o(n2n),n为物品个数。

5.1.2动态规划法

动态规划法是上世纪50年代RichardBellman创建的解决多阶段决策过程最优化的一种数学方法，即把多阶段决策问题变换为一系列相互联系单阶段问题，然后逐个加以解决。它的特点是解决多阶段、离散性问题。动态规划算法的基本思想是把原问题分解成一系列子问题,然后从这些子问题中求出原问题的解。对一个负重能力为C的背包,如果选择装入第i种物品,那么原背包问题就转化为负重能力为C-ci的子背包问题。动态规划算法是一种经典的背包问题求解算法，其原理简单，算法思路清晰，易于实现。动态规划算法虽然高效，但是对于规模