0-1背包问题求解方法综述

实用标准文案

算法分析与设计大作业

精彩文档

实验题目：组 员：班 级：指导老师：

0-1背包问题求解方法综述

实用标准文案

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)。 1.0-1背包问题描述

0-1背包问题(KP01)是一个著名的组合优化问题。它应用在许多实际领域,如项目选择、资源分布、投资决策等。背包问题得名于如何选择最合适的物品放置于给定背包中。本文主要研究背包问题中最基础的0/1背包问题的一些解决方法。

为解决背包问题，大量学者在过去的几十年中提出了很多解决方法。解决背包问题的算法有最优算法和启发式算法[2]，最优算法包括穷举法、动态规划法、分支定界法、图论法等，启发式算法包括贪心算法、遗传算法、蚁群算法、粒子算法等一些智能算法。

精彩文档

实用标准文案

0-1背包问题一般描述为：给定n种物品和一个背包。物品i的重量是w(i)，其价值为v(i)，背包的容量为c。问应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。

此问题的形式化描述是，给定c?0，wi?0，vi?0，1?i?n，要求找出一个n

（x1，x2，?，xn），xi?{0,1}，1?i?n，使得元0-1向量达到最大。

数学模型：max?vixi

i?1n?wixi?ci?1n，而且?vixi

i?1

n

约束条件：

?wx?c， x?{0,1},1?i?n

iii?1in2.0-1背包问题的求解算法

2.1蛮力算法（brute force method） 2.1.1基本思想：

对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。 2.1.2代码实现: #include #include using namespace std;

#define N 100 //最多可能物体数 struct goods //物品结构体 {

int sign; //物品序号 int w; //物品重量 int p; //物品价值 }a[N];

bool m(goods a,goods b)

精彩文档

实用标准文案

{

return (a.p/a.w)>(b.p/b.w); }

int max(int a,int b) {

return a

int n,C,bestP=0,cp=0,cw=0; int X[N],cx[N];

/*蛮力法求解0/1背包问题*/ int Force(int i) {

if(i>n-1){

if(bestP

for (int k=0;k

return bestP; }

cw=cw+a[i].w; cp=cp+a[i].p; cx[i]=1; //装入背包 Force(i+1); cw=cw-a[i].w; cp=cp-a[i].p;

cx[i]=0; //不装入背包 Force(i+1); return bestP; }

int KnapSack1(int n,goodsa[],int C,int x[]) {

Force(0); return bestP; }

int main()

精彩文档

实用标准文案

{

goods b[N];

printf(\物品种数n: \

scanf(\输入物品种数 printf(\背包容量C: \

scanf(\输入背包容量

for (int i=0;i

printf(\物品%d的重量w[%d]及其价值v[%d]: \ scanf(\ b[i]=a[i]; }

int sum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题 printf(\蛮力法求解0/1背包问题:\\nX=[ \ for(i=0;i

cout<

2.1.3复杂度分析：

蛮力法求解0/1背包问题的时间复杂度为：2^n 2.2贪心算法（Greedy algorithm）

贪心算法通过一系列的选择来得到问题的解。贪心选择即它总是做出当前最好的选择[4]。贪心选择性质指所求问题的整体最优解可以通过一系列局部最优选择，这是贪心算法与动态规划算法的主要区别。

贪心算法每次只考虑一步，每一步数据的选取都必须满足局部最优条件。在枚举剩下数据与当前已经选取的数据组合获得的解中，提取其中能获得最优解的唯一的一个数据，加入结果数据中，直到剩下的数据不能再加入为止[6]。贪心算法不能保证得到的最后解是最佳的，也不能用来求最大或最小解问题，只能求满足某些约束条件的可行解范围。

2.2.1算法设计

用贪心算法解决0-1背包问题一般有以下三种策略：

?价值最大者优先：在剩余物品中，选出可以装入背包的价值最大的物品，若背包有足够的容量，以此策略，然后是下一个价值最大的物品。但这种策略背包的承重量不能够得到有效利用，即得不到最优解。例如：

精彩文档

实用标准文案

n=3,w=[50,20,20],v=[10,7,7]c=55,得到的解是x=[1,0,0],这种方案的总价值为10，而最优解为[0,1,1],总价值为14。

?重量最小者优先：在剩余物品中，选择可以装入背包的重量最小的物品。但这种策略，不能保证重量小的是最有价值的，也不能得到最优解。例如：n=2,w=[10,20],v=[5,100],c=25，得到的解为x=[1,0],而最优解是[0,1]。

?单位价值最大者优先：根据价值与重量的比值vi/wi，即单位价值，在剩下的物品中依次选取比值最大的物品装入背包。这种策略也不能得到最优解。例如：n=3,w=[20,15,15],v=[40,25,25],vi/wi=[2,5/3,5/3],c=30,得到的解x=[1,0,0],而最优解是[0,1,1]。但它是直觉上的一个近似解。本文讨论该策略。

策略3的具体步骤为：

第一步：计算每个物品的价值比ri=vi/wi，i=1,2,…,n。 第二步：对物品的价值比非递增排序。

第三步：重复下面操作，直到有序列表中留下物品。如果列表中的当前物品能够装入背包，就将它放入背包中，否则，处理下一个物品。 2.2.2 编程实现 #include\#include #include #include using namespacestd;

#define max 100 //自定义物品最大数 void package(int v[],int w[],int n,int c) //定义包函数 {

doublea[max];

inti,totalv=0,totalw=0,index[max]; for(i=0;i

a[i]=(double)v[i]/w[i]; //单位价值计算 index[i]=i; }

for(i=1;i

for(int j=0;j

if(a[j]

double b=a[j]; a[j]=a[j+1]; a[j+1]=b;

精彩文档

实用标准文案

int c=v[j]; v[j]=v[j+1]; v[j+1]=c; int d=w[j]; w[j]=w[j+1]; w[j+1]=d;

int e=index[j];

index[j]=index[j+1]; index[j+1]=e; } } }

cout<<\单位价值：\输出单位价值 for(i=0;i

cout<

cout<

cout<

cout<

cout<

cout<

doublex[max]={0}; i=0;

while(w[i]<=c) {

x[i]=1; c=c-w[i]; i++; }

cout<<\所选择的商品如下:\

cout<<\序号i:\\t重量w:\\t价格v:\\t\输出所选择的商品 for(i=0;i

if(x[i]==1){

totalw=totalw+w[i]; totalv=totalv+v[i];

cout<

精彩文档

实用标准文案

} }

cout<<\背包的总重量为：\背包所装载总重量 cout<<\背包的总价值为：\背包的总价值 }

int main(void) //主函数定义 {

LARGE_INTEGER begin,end,frequency; QueryPerformanceFrequency(&frequency); srand(time(0)); int n,i,x[max];

int v[max],w[max],W; //变量的定义 cout<<\请输入物品种数n和背包容量W:\cin>>n>>W;

for(i=0;i

x[i]=0; //物品选择情况表初始化为0 for(i=0;i

v[i]=rand()00; w[i]=rand()00;}

cout<<\商品的重量和价值如下：\ for(int i=0;i

{ cout<

QueryPerformanceCounter(&begin);

package(v,w,n,W); //函数的调用 QueryPerformanceCounter(&end); cout<<\时间:\

<<(double)(end.QuadPart- begin.QuadPart) / frequency.QuadPart <<\}

2.2.2运行结果

精彩文档

实用标准文案

贪心算法求解0/1背包问题的时间复杂度为：(nlogn)

2.3 动态规划算法（Dynamic Programming）

20世纪50年代，美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，利用个阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划[3]。动态规划是基于递归的，通常不是一个解决KP有效的方式,因为空间消耗非常大,和最坏的和最好的计算工作通常是相同的[7]。动态规划算法与分治法类似，其基本思想也是将带求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法解决这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果我们能够保证已解决的子问题的答案，而在需要时找出已求出的答案，这样就可以避免大量的重复计算，从而达到多项式时间算法。为了达到此目的可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思想。具体的动态规划算法多种多样，但它们有相同的填表格式。

动态规划算法适用于解最优化问题。通常可按以下4个步骤设计： （1）找出最优解的性质，并刻画其结构特征。 （2）递归地定义最优值。

精彩文档

实用标准文案

（3）以自底向上的方式计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解。

步骤（1）~（3）是动态规划算法的基本步奏。在需要求出最优值的情形，步骤（4）可以省去。若需要求出问题的最优解，则必须执行步骤（4）.此时，在步骤（3）中计算最优解时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。

使用动态规划求解问题，最重要的就是确定动态规划3要素：（1）问题的阶段；（2）每个阶段的状态；（3）从前一个阶段转化后一个阶段之间的递推关系[4]。

2.3.1分析最优解的性质，刻画最优解的结构特征——最优子结构性质分析 设所给0-1背包问题的一个最优解，则是下（x1，x2，?，xn）（x2，x3?，xn）面相应子问题的一个最优解： 目标函数：maxnn?vx

iii?2 约束条件：

?wxi?2nii?c?w1x1,xi?{0,1}(2?i?n)

证明：若不是上述子问题的一个最优解，而是他的（x2，x3?，xn）（y2，y3，?，yn）最优解。由此可知，?viyi??vixi且w1x1??wiyi?c。因此

i?2i?2nnv1x1??viy1??vixi

i?2ni?1nn

w1x1??wiyi?ci?2（x1，y2，?，yn）（y1，y2，?，yn）这说明是原问题的一个更优解，从而不是所给原问题的最优解，产生矛盾。

（x2，x3?，xn）所以是上述子问题的一个最优解。 2.3.2递归关系

（x1，x2，?，xn） 由于0-1背包问题的解是用向量来描述的。因此，该问题可（x1，x2，?，xn）以看做是决策一个n元0-1向量。对于任意一个分量xi的决策是?，xi?1)已被确“决定xi=1或xi=0，i=1,2,…,n。对xi?1决策后，序列(x1，x2，定，在决策xi时，问题处于下列两个状态之一：

精彩文档

实用标准文案

（1）背包容量不足以装下物品i，则=0，装入背包的价值不增加； （2）背包容量足以装入物品i,则=1，装入背包的价值增加vi。 在这种情况下，装入背包的价值最大化应该是对决策后的价值。 设所给0-1背包问题的子问题

max?vkxkk?in?wxknk?j，xk?(0,1)，i?k?n

k?i的最优值为m(i,j),即m(i,j)是背包容量为j，可选择的物品为i,i+1,…,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m（i,j）的递归式为：

m(i,j)?{max{m(i?1,j),m(i?1,j?wi)?vi}(j?wi)m(i?1,j)(0?j?wi)vn，j?wn0，0?j?wn

m(n,j)?{2.3.3算法设计

基于上面的讨论，求解0-1背包的动态规划算法步骤如下：

步骤1：当wi(1?i?n)为正整数时，用数组w[n]来存放n个物品的重量；数组v[n]来存放n个物品的价值，背包容量为c，数组M[n+1][c+1]来存放每一次迭代的执行结果；数组x[n]用来存储所装入背包的物品状态； 步骤2：初始化。数组M的第0行第0列全部设置为0；

步骤3：循环阶段。按式（5）确定前i个物品能够装入背包的情况下得到的最优值；

步骤3-1：i=1时，求出M[1][j],1≤j≤c； 步骤3-2：i=2时，求出M[2][j],1≤j≤c； ……

步骤3-n:i=n时，求出M[n][c]。此时，M[n][c]便是最优值；

步骤4：确定装入背包的具体物品。从M[n][c]的值向前推，如果M[n][c]>M[n-1][c]，表明第n个物品被装入背包，则xn=1，前n-1个物品没有被装入背包，则xn=0，前n-1个物品被装入容量为c的背包中。以此类推，知道确定第1个物品是否被装入背包为止。由此，得到下面的关系式： 如果M[i][j]=M[i-1][j],说明第i个物品没有被装入背包，则xi=0；

精彩文档

实用标准文案

如果M[i][j]>M[i-1][j],说明第i个物品被装入背包，则xi=1，j=j-wi。 按照上述关系式，从M[n][c]的值向前倒推，即j初始为c，i初始为n,即可确定装入背包的具体物品。

上述算法需要O（nc）时间计算时间。不过上述算法有2个明显的确点。一是算法要求所给物品的重量wi（1≤i≤n）是整数；二是当背包容量c很大时，算法需要的计算时间较多。 2.2.2运行结果

贪心算法求解0/1背包问题的时间复杂度为：O（nm） 2.4 回溯法（Backtracking） 2.4.1回溯法0-1背包问题的实现

回溯法是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包，以便获得的收益最大，则解空间应组织成子集树的形状。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。

左子树表示一个可行的结点，无论何时都要移动到它，当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是r为还未遍历的对象的收益之和，将r加到cp(当前节点所获收益)之上，若( r+cp) <=bestp(目前最优解的收益)，则不需搜索右子树。一种更有效的方法是按收益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量。

精彩文档

实用标准文案

2.4.2 编程实现如下

#include\#include #include #include #include using namespace std;

#defineN 100 //最多可能物体数 structgoods //物品结构体 {

int sign; //物品序号 int w; //物品重量 int p; //物品价值 }a[N],b[N];

bool m(goods a,goods b) {

return (a.p/a.w)>(b.p/b.w); }

int max1(int a,intb) //最大函数定义 {

return a

int n,W,bestP=0,cp=0,cw=0;

int X[N],cx[N]; //变量定义 int BackTrack(int i) {

if(i>n-1){

if(bestP

for (int k=0;k

returnbestP; }

if(cw+a[i].w<=W){ //进入左子树 cw=cw+a[i].w; cp=cp+a[i].p; cx[a[i].sign]=1; //装入背包 BackTrack(i+1); cw=cw-a[i].w; cp=cp-a[i].p; //回溯，进入右子树 }

cx[a[i].sign]=0; //不装入背包 BackTrack(i+1); return bestP;

精彩文档

实用标准文案

}

void KnapSack3(intn,goods a[],int C,intx[]) {

int totalW=0;

for(inti=0;i

x[i]=0;

a[i].sign=i; }

sort(a,a+n,m); //将各物品按单位重量价值降序排列 BackTrack(0);

cout<<\所选择的商品如下:\

cout<<\序号i:\\t重量w:\\t价格v:\\t\

for(int i=0;i

if(X[i]==1){

cout<

cout<<\放入背包的物品总重量为：\ cout<

cout<<\放入背包的物品总价值为：\}

int main() //主函数的定义 {

LARGE_INTEGER begin,end,frequency; QueryPerformanceFrequency(&frequency); srand(time(0));

cout<<\请输入物品种数n和背包容量W:\ cin>>n>>W;

for (inti=0;i

a[i].w=rand()00; a[i].p=rand()00; b[i]=a[i]; }

cout<<\物品的重量和价值分别如下：\

for (inti=0;i

cout<

cout<

精彩文档

实用标准文案

}

QueryPerformanceCounter(&begin);

KnapSack3(n,a,W,X); //调用回溯法求0/1背包问题 QueryPerformanceCounter(&end); cout<<\时间:\

<<(double)(end.QuadPart- begin.QuadPart) / frequency.QuadPart

<<\

} 2.4. 3 运行结果

回溯法法的时间复杂度为

2.5分枝-限界法（Branch - threshold method） 2.5.1 分枝-限界法的基本原理与分析

分枝限界法是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-结点的扩充方式。每个活结点有且仅有一次会变成E-结点。当一个结点变为E-结点时，则生成从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不可能导出最优解的结点，其余结点加人活结点表，然后从表中选择一个结点作为下一个E结点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充才结束。

2.5.2 分枝限界0-1背包问题的实现

首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。

精彩文档

实用标准文案

算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。

2.5.3 编程实现如下 #include #include using namespace std; #define N 100 struct goods {

int sign; int w; int p; }a[N];

bool m(goods a,goods b) {

return (a.p/a.w)>(b.p/b.w); }

int max(int a,int b) {

return a

int n,C,bestP=0,cp=0,cw=0; int X[N],cx[N]; struct KNAPNODE {

bool s1[N]; int k; int b; int w; int p; };

struct HEAP {

//堆元素结构体

//当前放入物体 //搜索深度 //价值上界 //物体重量 //物体价值

//状态结构体

//物品序号 //物品重量 //物品价值

//最多可能物体数 //物品结构体

精彩文档

实用标准文案

KNAPNODE *p; };

//结点数据 //所指结点的上界

int b;

void swap(HEAP &a, HEAP&b) //交换两个堆元素 {

HEAP temp = a; a = b; b = temp; }

//堆中元素上移

void mov_up(HEAP H[], int i) {

bool done = false; if(i!=1){ }

//堆中元素下移

void mov_down(HEAP H[], intn, int i) {

bool done = false; if((2*i)<=n){

while(!done && ((i = 2*i) <= n)){

if(i+1<=n && H[i+1].b > H[i].b){ }

if(H[i/2].b

swap(H[i/2], H[i]); i++;

while(!done && i!=1){ }

if(H[i].b>H[i/2].b){ } i = i/2;

swap(H[i], H[i/2]); done = true; }else{

}

精彩文档

实用标准文案

}

}

}else{ }

done = true;

}

//往堆中插入结点

void insert(HEAP H[], HEAPx, int &n) { n++; H[n] = x; mov_up(H,n); }

//删除堆中结点

void del(HEAP H[], int&n, int i) {

HEAP x, y;

x = H[i]; y = H[n]; n --; if(i<=n){ }

//获得堆顶元素并删除

HEAP del_top(HEAP H[], int&n) {

HEAP x = H[1]; del(H, n, 1); return x; }

H[i] = y; if(y.b>=x.b){ }

mov_up(H,i); mov_down(H, n, i); }else{

}

精彩文档

实用标准文案

//计算分支节点的上界

void bound( KNAPNODE* node,int M, goods a[], int n) {

int i = node->k; float w = node->w; float p = node->p; if(node->w>M){ }

//用分支限界法实现0/1背包问题

int KnapSack4(int n,goodsa[],int C, int X[]) {

int i, k = 0; int v;

KNAPNODE *xnode, *ynode, *znode; HEAP x, y, z, *heap;

heap = new HEAP[n*n]; // 分配堆的存储空间 for( i=0; i

a[i].sign=i;

//记录物体的初始编号

// 对物体按照价值重量比排序

}

sort(a,a+n,m);

xnode = new KNAPNODE; // 建立父亲结点 for( i=0; i

xnode->s1[i] = false;

// 堆中元素个数的计数器初始化为0

}else{

while((w+a[i].w<=M)&&(i

node->b = p + (M - w)*a[i].p/a[i].w; node -> b = p; }else{

w += a[i].w;

// 计算背包已装入载重

// 计算背包已装入价值

p += a[i++].p;

// 物体重量超过背包载重量 // 上界置为0

node->b = 0;

}

精彩文档

实用标准文案

}

xnode->k = xnode->w = xnode->p = 0; while(xnode->k

ynode = new KNAPNODE; *ynode = *xnode;

// 建立结点y

//结点x的数据复制到结点y

ynode->s1[ynode->k] = true; // 装入第k个物体 ynode->w += a[ynode->k].w; // 背包中物体重量累计 ynode->p += a[ynode->k].p; // 背包中物体价值累计 ynode->k ++; bound(ynode, C, a, n); y.b = ynode->b; y.p = ynode;

znode = new KNAPNODE; // 建立结点z

*znode = *xnode; //结点x的数据复制到结点z znode->k++; // 搜索深度++ bound(znode, C, a, n); z.b = znode->b; z.p = znode;

insert(heap, z, k); delete xnode;

x = del_top(heap, k); xnode = x.p;

//获得堆顶元素作为新的父亲结点 //结点z按上界的值插入堆中 //计算节点z的上界

// 搜索深度++

// 计算结点y的上界

insert(heap, y, k); //结点y按上界的值插入堆中

}

v = xnode->p;

for( i=0; i

if(xnode->s1[i]){ }

X[a[i].sign] =1 ; X[a[i].sign] = 0; }else{

//取装入背包中物体在排序前的序号

}

delete xnode; delete heap;

return v;

//返回背包中物体的价值

精彩文档

实用标准文案

}

/*测试以上算法的主函数*/ int main() {

goods b[N];

printf(\物品种数n: \ scanf(\

//输入物品种数 //输入背包容量

printf(\背包容量C: \ scanf(\ {

printf(\物品%d的重量w[%d]及其价值v[%d]: \scanf(\b[i]=a[i];

//调用分支限界法求0/1背包问题

for (int i=0;i

}

intsum4=KnapSack4(n,a,C,X);

printf(\分支限界法求解0/1背包问题:\\nX=[ \ for(i=0;i

cout<

printf(\装入总价值%d\\n\ return 0; }

2.5. 4 运行结果

精彩文档

实用标准文案

分支限界法求解0/1背包问题的时间复杂度为：

2.6遗传算法（Genetic algorithm）

遗传算法是模拟达尔文的生物自然选择学说和自然界的生物进化过程的一种自适应全局概率搜索算法[2]。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和良好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定规则。

遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子）进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。 2.6.1算法设计

遗传算法解决0-1背包问题的基本步骤如下：

（1）群体的初始化：确定种群规模M,交叉概率pc、变异概率pm、染色体长度N即最大进化代数T。随机初始化染色体，给出物体体积、物品价值v和背包容量c。 （2）产生遗传编码：采用二进制n维矢量解X作为解空间参数的遗传编码，串的长度等于n,xi=1表示该物体装入背包，xi=0表示该物品没有被装入背包。 （3）适应度函数的构造：适应度函数的建立是解决背包问题的关键。首先背包问题的目标函数和约束条件文章前面已提出 数学模型：max 约束条件：

?vxii?1ni

?wx?c， x?{0,1},1?i?n

iii?1in现给出构造它的2种适应度函数：

精彩文档

实用标准文案

(1)F??vixi,其中xi?1或（0i?1,2,?，n）n

(2)F?(?vixi)k,其中k?1.00125，其中xi?1或（0i?1,2,?，n）ni?1i?1

（4）选择操作：根据选择概率选择染色体，将上述的个体作为第一代，采用以正比于适应度的赌轮随机选择方式，每个个体适应度值为fi，则i被选中的概率Pis?fi/?fi；对于初始化后的种群，先计算出每条染色体的适应度

i?1n值，再计算出其被选择的概率，将它们进行比较，把选择概率最小的一条染色体淘汰掉，并选择概率最大的一条染色体进行复制，用这条复制的染色体代替淘汰的染色体的位置。

（5）交叉操作：判断染色体是否为活的染色体，若为活的染色体，则将染色体进行交叉，一般采用一点交叉方式，交叉概率为Pc，具体操作是在个体串中随机设定一个交叉点，实行交叉时，该点前后的两个个体的部分结构进行互换，并生成两个新的个体。

（6）变异操作：染色体变异采用位点变异的方式。位点变异比较简单，对于0-1背包问题来说，就是把染色体的变异位1变为0,0变为1，其他位保持不变。变异概率为Pm，变异的目的是使其变异后的适应度大于或等于其原适应度。先选择一个变异位进行变异，再计算它的适应度，看它是否大于或等于其原来的适应度，若不是的话就重新选择变异位进行变异操作。对种群依次进行选择、交叉、变异后就检验得到的新个体，当某代得到的结果满足要求或当前代数等于结束代数时算法结束得到结果，否则重新选择、交叉、变异操作，直到得到满意的结果为止。

使用幂函数适应度函数的遗传算法全局搜索效率比较高[2]。

3算法分析与比较

通过上面几种算法基本原理的介绍和分析，得到了不同方法解决NP难的0-1背包问题。下面从时间、空间复杂度、准确性等方面进行进一步的分析比较。

动态规划算法的空间和时间复杂度由物品的数量和背包的承重量来决定。若物品数量为n,背包承重量为c,初始化数组需要空间为O（nc）,两重for循环时间复杂度为O(nc)。动态规划能够保证求解的正确性，但它速度慢，空间消耗大。

贪心算法的时间复杂度为O(nlogn)。但贪心算法属于近似算法，速度快，时间消耗少，但不能确定结果为最优解，体现了该算法的局限性。

遗传算法跟贪心算法一样，也是一种近似算法。它的时间复杂度取决于采用的适应度函数。第一种适应度函数对遗传算法的参数比较敏感，幂函数的适应度函数的遗传函数能获得高质量的解。 3.1 算法的效率分析

精彩文档

实用标准文案

（1）蛮力法

对于一个有n个元素的集合，其子集数量为2^n，所以，不论生成子集的算法效率有多高，蛮力法都会导致一个2^n的算法 （2）贪心法

贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似解。贪心算法的时间复杂度为O(nlogn）。 （3）动态规划法

从m(i，j)的递归式容易看出，算法Knaspack需要O(nc)计算时间; Traceback需O(n)计算时间；算法总体需要O(nc)计算时间。 （4）回溯法

由于计算上界函数需要O(n)时间，在最坏情况下有个右孩子结点需要上界函数，故计算0-1背包问题的回溯算法所需的计算时间复杂度为。对回溯法的改进主要是对判断是否移动右子树上，一种更有效的方法是按效益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量，当遇到第一个不能全部放人背包的对象时，就使用它的一部分。

回溯算法的运行时间取决于它在搜索过程中所生成的结点数,而限界函数可以大量减少所生成的结点个数,省去许多无谓的搜索, 使得搜索速度更快,其调用限界函数计算上界需花费O(n)时间 ,最坏情况下有个结点需调用限界函数 ,需花费O(n)时间,所以该算法的时间复杂度为。 (5) 分枝-限界法

分支限界法求解0/1背包问题的时间复杂度为：

为了直观表示，特将四种算法的时间复杂度总结如下：

精彩文档

实用标准文案

（1）为了更好地说明问题，现在对不同问题规模三种不同算法所需要的时间进行比较。随着问题规模的增大，各算法的计算时间都在增大，由于回溯法相对于其他算法所增加的时间更加显著，特此，单独考虑回溯法的情况。

（2）此种情况下背包的容量为100，不同问题规模回溯法所用时间所下表所示

5 由以上测试时间可以很好的验证，当背包容量和问题规模达到一定程度时，用回溯法解决背包问题，因此随着物件数n的增大，其解的空间将以 级增长，当n大到一定程度上，用此算法解决背包问题将是不现实的。这正好与理论分析的情况是一致的。

6 从实验中也可以发现，当问题规模很小的时候，四种算法都有较好的稳定性，计算时间都相差不多。随着问题规模的增大，各算法的计算时间差别逐渐显现出来。

7 对比以上四种算法可以看出，各种算法都有自己的特点，贪心算法速度比较快，但是所得的解有时可能只是局部最优解；分枝限界法需要的解空间。故该算法不常用在背包问题求解；回溯法比分枝限界在占用内存方面具有优势。回溯法占用的内存是0(解空间的最大路径长度)，而分枝限界所占用的内存为0(解空间大小)。对于一个子集空间，回溯法需要0(n)的内存空间，而分枝限界则需要的空间。虽然最大收益或最小耗费分枝限界在直觉上要好于回溯法，并且在许多情况下可能会比回溯法检查更少的结点，但在实际应用中，它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。

解决背包问题算法比较结果

精彩文档

实用标准文案

4结论

目前，0-1背包问题还没有找到完美的求解最优解的方法，现在的智能算法都只能在一定的范围求解，各种算法都有一定的局限性[6]。对于0-1背包问题的探索，一方面要在现有的算法如动态规划算法，贪心算法等算法上改进和完善，还要在其他学科的算法中获得启示，如从生物中得到启示的遗传算法，研究出解决0-1背包的新算法。0-1背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成0-1背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。从计算复杂性理论看，背包问题是 NP 完全问题。半个多世纪以来，该问题一直是算法与复杂性研究的热门话题。通过对 0-1 背包问题的算法研究可以看出，回溯法和分枝限界法等可以得到问题的最优解，可是计算时间太慢；动态规划法也可以得到最优解，当m>2^n时，算法需要 n2^n 的计算时间，这与回溯法存在一样的缺点——计算速度慢；采用贪心算法，虽然耗费上优于前者，但是不一定是最优解。目前，以上几种方法中回溯法、动态规划法、贪心法都广泛地应用到不同的实际问题中，并在应用中不断地改进。

5参考文献：

[1]王晓东. 计算计算法设计与分析[M]. 北京：电子工业出版社，2003 [2]程春英，张玉春. 利用遗传算法求解0/1背包问题[A]. 内蒙古民族大学学报（自然科学版）第25卷，第6期，2010

[3]吕聪颖，赵刚彬，周春光. 求解0—1背包问题的动态规划法分析[A]. 南阳理工学院学报第3卷第2期，2011

[4]曹亚非. 背包问题中贪心算法的应用探讨[A]. Valley Silicon

[5]曹珊珊. 动态规划算法在0/1背包问题中的应用与分析[A]. 信息产业

[6]李雯瑞. 0—1背包问题的求解算法设计与分析[A]. 软件导刊 第11卷 第6期，2012

精彩文档