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背包问题。此问题的形式化描述是，给定，要求找出一个n元0-1向量，使得，而且达到最大。数学模型：约束条件： ， 2.0-1背包问题的求解算法2.1蛮力算法（brute force method）2.1.1基本思想：对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。2.1.2代码实现:#include#includeusing namespace std;#define N 100 /最多可能物体数struct goods /物品结构体 int sign; /物品序号 int w; /物品重量 int p; /物品价值aN;bool m(goods a,goods b) return (a.p/a.w)(b.p/b.w);int max(int a,int b) return an-1) if(bestPcp&cw+ai.w=C) for (int k=0;kn;k+) Xk=cxk;/存储最优路径 bestP=cp; return bestP; cw=cw+ai.w; cp=cp+ai.p; cxi=1; /装入背包 Force(i+1); cw=cw-ai.w; cp=cp-ai.p; cxi=0; /不装入背包 Force(i+1); return bestP;int KnapSack1(int n,goodsa,int C,int x) Force(0); return bestP;int main() goods bN; printf(物品种数n: ); scanf(%d,&n); /输入物品种数 printf(背包容量C: ); scanf(%d,&C); /输入背包容量 for (int i=0;in;i+) /输入物品i的重量w及其价值v printf(物品%d的重量w%d及其价值v%d: ,i+1,i+1,i+1); scanf(%d%d,&ai.w,&ai.p); bi=ai; int sum1=KnapSack1(n,a,C,X);/调用蛮力法求0/1背包问题 printf(蛮力法求解0/1背包问题:nX= ); for(i=0;in;i+) coutXi ;/输出所求Xn矩阵 printf( 装入总价值%dn,sum1); bestP=0,cp=0,cw=0;/恢复初始化2.1.3复杂度分析：蛮力法求解0/1背包问题的时间复杂度为：2n2.2贪心算法（Greedy algorithm） 贪心算法通过一系列的选择来得到问题的解。贪心选择即它总是做出当前最好的选择4。贪心选择性质指所求问题的整体最优解可以通过一系列局部最优选择，这是贪心算法与动态规划算法的主要区别。 贪心算法每次只考虑一步，每一步数据的选取都必须满足局部最优条件。在枚举剩下数据与当前已经选取的数据组合获得的解中，提取其中能获得最优解的唯一的一个数据，加入结果数据中，直到剩下的数据不能再加入为止6。贪心算法不能保证得到的最后解是最佳的，也不能用来求最大或最小解问题，只能求满足某些约束条件的可行解范围。2.2.1算法设计用贪心算法解决0-1背包问题一般有以下三种策略：价值最大者优先：在剩余物品中，选出可以装入背包的价值最大的物品，若背包有足够的容量，以此策略，然后是下一个价值最大的物品。但这种策略背包的承重量不能够得到有效利用，即得不到最优解。例如：n=3,w=50,20,20,v=10,7,7c=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。单位价值最大者优先：根据价值与重量的比值/，即单位价值，在剩下的物品中依次选取比值最大的物品装入背包。这种策略也不能得到最优解。例如：n=3,w=20,15,15,v=40,25,25,/=2,5/3,5/3,c=30,得到的解x=1,0,0,而最优解是0,1,1。但它是直觉上的一个近似解。本文讨论该策略。策略3的具体步骤为：第一步：计算每个物品的价值比=/，i=1,2,n。第二步：对物品的价值比非递增排序。第三步：重复下面操作，直到有序列表中留下物品。如果列表中的当前物品能够装入背包，就将它放入背包中，否则，处理下一个物品。2.2.2 编程实现#includestdafx.h#include #include #includeusing namespacestd;#define max 100 /自定义物品最大数void package(int v,int w,int n,int c) /定义包函数 doubleamax; inti,totalv=0,totalw=0,indexmax; for(i=0;in;i+) ai=(double)vi/wi; /单位价值计算 indexi=i; for(i=1;in;i+) for(int j=0;jn-i;j+) if(ajaj+1) /进行循环判断 double b=aj; aj=aj+1; aj+1=b; int c=vj; vj=vj+1; vj+1=c; int d=wj; wj=wj+1; wj+1=d; int e=indexj; indexj=indexj+1; indexj+1=e; cout单位价值：; /输出单位价值 for(i=0;in;i+) coutai ; coutendl物品价值：; /输出物品价值 for(i=0;in;i+) coutvit; coutendl物品重量：; /输出物品重量 for(i=0;in;i+) coutwit; coutendl; doublexmax=0; i=0; while(wi=c) xi=1; c=c-wi; i+; cout所选择的商品如下:endl;cout序号i:t重量w:t价格v:tendl; /输出所选择的商品 for(i=0;in;i+)if(xi=1)totalw=totalw+wi;totalv=totalv+vi;coutindexi+1twitviendl; cout背包的总重量为：totalwendl; /背包所装载总重量cout背包的总价值为：totalvendl; /背包的总价值int main(void) /主函数定义 LARGE_INTEGER begin,end,frequency; QueryPerformanceFrequency(&frequency); srand(time(0); int n,i,xmax;int vmax,wmax,W; /变量的定义coutnW;for(i=0;in;i+)xi=0; /物品选择情况表初始化为0for(i=0;in;i+)vi=rand()%1000;wi=rand()%1000;cout商品的重量和价值如下：endl; for(int i=0;in;i+) coutwit; coutviendl; QueryPerformanceCounter(&begin); package(v,w,n,W); /函数的调用 QueryPerformanceCounter(&end); cout时间: (double)(end.QuadPart- begin.QuadPart) / frequency.QuadPart sMn-1c，表明第n个物品被装入背包，则=1，前n-1个物品没有被装入背包，则=0，前n-1个物品被装入容量为c的背包中。以此类推，知道确定第1个物品是否被装入背包为止。由此，得到下面的关系式：如果Mij=Mi-1j,说明第i个物品没有被装入背包，则=0；如果MijMi-1j,说明第i个物品被装入背包，则=1，j=j-。按照上述关系式，从Mnc的值向前倒推，即j初始为c，i初始为n,即可确定装入背包的具体物品。上述算法需要O（nc）时间计算时间。不过上述算法有2个明显的确点。一是算法要求所给物品的重量（1in）是整数；二是当背包容量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 编程实现如下#includestdafx.h#include#include#include #includeusing namespace std;#defineN 100 /最多可能物体数structgoods /物品结构体int sign; /物品序号int w; /物品重量int p; /物品价值aN,bN;bool m(goods a,goods b)return (a.p/a.w)(b.p/b.w);int max1(int a,intb) /最大函数定义return an-1)if(bestPcp)for (int k=0;kn;k+) Xk=cxk;/存储最优路径bestP=cp;returnbestP;if(cw+ai.w=W) /进入左子树cw=cw+ai.w;cp=cp+ai.p;cxai.sign=1; /装入背包BackTrack(i+1);cw=cw-ai.w;cp=cp-ai.p; /回溯，进入右子树cxai.sign=0; /不装入背包BackTrack(i+1);return bestP;void KnapSack3(intn,goods a,int C,intx)int totalW=0;for(inti=0;in;i+)xi=0;ai.sign=i;sort(a,a+n,m);/将各物品按单位重量价值降序排列BackTrack(0);cout所选择的商品如下:endl;cout序号i:t重量w:t价格v:tendl;for(int i=0;in;i+) /进行循环输出 if(Xi=1)couti+1t;totalW+=bi.w;coutbi.wt;coutbi.pendl;cout放入背包的物品总重量为：totalW;coutendl;cout放入背包的物品总价值为：bestPendl; int main() /主函数的定义LARGE_INTEGER begin,end,frequency; QueryPerformanceFrequency(&frequency); srand(time(0); coutnW;for (inti=0;in;i+)/输入物品i的重量w及其价值vai.w=rand()%1000;ai.p=rand()%1000;bi=ai;cout物品的重量和价值分别如下：endl;for (inti=0;in;i+)/输入物品i的重量w及其价值vcoutai.w;coutt;coutai.pendl;QueryPerformanceCounter(&begin);KnapSack3(n,a,W,X);/调用回溯法求0/1背包问题QueryPerformanceCounter(&end); cout时间: (double)(end.QuadPart- begin.QuadPart) / frequency.QuadPart sendl; 2.4. 3 运行结果回溯法法的时间复杂度为2.5分枝-限界法（Branch - threshold method）2.5.1 分枝-限界法的基本原理与分析分枝限界法是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-结点的扩充方式。每个活结点有且仅有一次会变成E-结点。当一个结点变为E-结点时，则生成从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不可能导出最优解的结点，其余结点加人活结点表，然后从表中选择一个结点作为下一个E结点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充才结束。2.5.2 分枝限界0-1背包问题的实现首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。2.5.3 编程实现如下#include#includeusing namespace std;#define N 100 /最多可能物体数struct goods /物品结构体 int sign; /物品序号 int w; /物品重量 int p; /物品价值aN;bool m(goods a,goods b) return (a.p/a.w)(b.p/b.w);int max(int a,int b) return aHi/2.b)swap(Hi, Hi/2);elsedone = true;i = i/2; /堆中元素下移void mov_down(HEAP H, intn, int i) bool done = false; if(2*i)=n)while(!done & (i = 2*i) = n)if(i+1 Hi.b)i+;if(Hi/2.bHi.b)swap(Hi/2, Hi);elsedone = true; /往堆中插入结点void insert(HEAP H, HEAPx, int &n) n+; Hn = x; mov_up(H,n);/删除堆中结点void del(HEAP H, int&n, int i) HEAP x, y; x = Hi; y = Hn; n -; if(i=x.b)mov_up(H,i);elsemov_down(H, n, i); /获得堆顶元素并删除HEAP del_top(HEAP H, int&n) HEAP x = H1; del(H, n, 1); return x;/计算分支节点的上界void bound( KNAPNODE* node,int M, goods a, int n) int i = node-k; float w = node-w; float p = node-p; if(node-wM) / 物体重量超过背包载重量node-b = 0; / 上界置为0 elsewhile(w+ai.w=M)&(in) w += ai.w; / 计算背包已装入载重p += ai+.p; / 计算背包已装入价值if(ib = p + (M - w)*ai.p/ai.w;elsenode - b = p; /用分支限界法实现0/1背包问题int KnapSack4(int n,goodsa,int C, int X) int i, k = 0; / 堆中元素个数的计数器初始化为0 int v; KNAPNODE *xnode, *ynode, *znode; HEAP x, y, z, *heap; heap = new HEAPn*n; / 分配堆的存储空间 for( i=0; in; i+)ai.sign=i; /记录物体的初始编号 sort(a,a+n,m); / 对物体按照价值重量比排序 xnode = new KNAPNODE; / 建立父亲结点 for( i=0; is1i = false; xnode-k = xnode-w = xnode-p = 0; while(xnode-ks1ynode-k = true; / 装入第k个物体ynode-w += aynode-k.w; / 背包中物体重量累计ynode-p += aynode-k.p; / 背包中物体价值累计ynode-k +; / 搜索深度+bound(ynode, C, a, n); / 计算结点y的上界y.b = ynode-b;y.p = ynode; insert(heap, y, k); /结点y按上界的值插入堆中znode = new KNAPNODE; / 建