背包问题

背包问题

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

一、定义：

背包问题属于组合优化问题，一般的最优化问题由目标函数和约束条件两部部分组成：

我们有n种物品，物品i的重量为wi，价格为pi。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。

如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。可以用公式表示为：

1maxniiipx

1..,niiiSTwxW 0,1ix

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

1maxniiipx

1..,niiiSTwxW 0,1,,iixb

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

各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解。

二、基本模型的建立方法

1、0-1背包问题的数学模型（最基础的背包问题）

分类：0-1背包问题简单分为一维背包和二维背包问题。

特点：每种物品仅有一件，可以选择放或不放。

1.1 一维背包问题

问题：一个旅行者准备进行徒步旅行，为此他必须决定携带若干物品。设有n件物品可供他选择，编号为1,2,...,n第i件物品重量为iw千克，价值为ip元，他能携带的最大重量为w千克。他应该装入哪几件物品价值最大。

解：引入变量ix，且设

1,(1,2,,)0,iixini表示将第种物品装入包中表示不将第种物品装入包

背包问题报告

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

小组分工情况

小组成员 查找资料 制作ppt 编写程序 讲解ppt 制作报告

张灿 ⅴ ⅴ ⅴ ⅴ ⅴ

吴雪涛 ⅴ

高坤 ⅴ ⅴ

占强 ⅴ

习慧平 ⅴ

背包问题

一、背包问题的历史由来

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

二、背包问题的描述

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

也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？

三、背包问题的定义

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

1

0-1背包问题

计科一班 李振华 2012040711

1、 问题描述

给定n种物品和一背包，物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品（物品不能分割），使得装入背包中物品的总价值最大?

抽象描述如下：

x[n]:表示物品的选择，x[i]=1表示选择放进物品i到背包中。

2、 问题分析

推导过程（最优子结构证明，最优值递归定义）

1、 动态规划法算法

1.抽象之后背包问题转换为找到一个最优的数组，x1，x2，.....,xn的0-1序列。

2.假设最优解的序列为x1，x2，.....,xn，能使背包容量C的总价值最大.

如果，x1=1，则x2,...,xn是C-w1容量的背包的总价值依然是最大的序列；

如果，x1=0，则x2,....,xn是C容量的背包的总价值依然是最大的序列。

这就是我们所说的最优子结构性质。

3.进一步分析：我们用m(i,j)表示为已经判断好了i:n的序列的背包最大价值，并且此时的背包剩余的容量为j，对物品i进行判断

如果j>wi, 就只要做出选择wi和不选择wi情况下，哪种更能使背包的总价值更大：m(i,j)=max{ m(i+1,j),m(i+1,j-wi)+vi}(注意这是个递归式)

如果j

初始化： m(n,j)=vn (j>= wn)；

m(n,j)=0 (0<=j< wn)

m(0,C)=0

最终的结果：m(1,C)

4.如果单纯的从利用递归，重复计算了很多的值，耗费的时间是很大的，动态规划还需避免这种重复计算，怎样自顶向下或自底向上的计算呢？ 2

采用列表的方法就可以很好的分析设计自顶向下或自底向上的计算的算法了

算法实验报告

---背包问题

实验目的

1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。

2．熟练掌握分阶段的和递推的最优子结构分析方法。

3．学会利用动态规划算法解决实际问题。

问题描述：

给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值为vi，背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，背包的容积d，物品的个数n。接下来的n行表示n个物品的重量、体积和价值。输出为最大的总价值。

问题分析:

标准0-1背包问题，MaxV表示前i个物品装入容量为j的背包中时所能产生的最大价值，结构体objec表示每一个可装入物品，其中w表示物品的重量，v表示物品的价值。如果某物品超过了背包的容量，则该物品一定不能放入背包，问题就变成了剩余i-1个物品装入容量为j的背包中所能产生的最大价值；如果该物品能装入背包，问题就变成i-1个物品装入容量为j-objec[i].w的背包所能产生的最大价值加上物品i的价值objec[i].v.

复杂性分析

时间复杂度，最好情况下为0，最坏情况下为：（abc）

源程序

#include

#include

#include

#include

#include

int V [200][200][200];

int max(int a,int b)

{ if(a>=b)

return a;

else

return b;

}

int KnapSack(int n,int w[],int z[],int v[],int x[],int c,int b)

{

int i,p,q;

for(i=0;i<=n;i++)

V[i][0][0]=0;