0-1背包问题的算法决策分析

来源:用户上传      作者:

　　摘要：0-1背包问题是算法中的经典问题，现实中应用广泛，它是属于NP难问题。该文就0-1背包问题的三种策略：动态规划、贪心算法、回溯和分支限界策略进行了分析。主要从三种策略的基本思想、求解方法包括主要关键代码和算法时间复杂度几个方面进行阐述，从而分析了当遇到具体问题，如何决策使用哪种策略解决问题。
　　关键词：0-1背包问题;动态规划;贪心算法;回溯法;分支限界法;时间复杂
　　中图分类号：TP311.1
　　文献标识码：A
　　文章编号：1009-3044（2020）04-0259-02
　　收稿日期：2019-11-27
　　作者简介：鄢莉（1978—），女，四川人，副教授，研究生，研究方向为计算机应用及算法。
　　Algorithmic Decision Analysis of 0-1 Knapsack Problem
　　YAN Li
　　（Panzhihua University，Panzhihua 6 17000，China
　　Abstract：In algorithm 0-1 knapsack problem is a classical problem.It is widely used in reality，which belongs to NP-hard problem.This paper discusses three strategies for 0-1 knapsack problem，as Dynamic Programming，Greedy Algorithm，Backtracking and Branch-and-Bound.Based on the basic ideas and solving methods，including the main key codes and the time complexity of the algorithm，this paper analyses how to use strategy to solve the specific problems.
　　complexity Key words：0-1 knapsack problem;dynamic programming;greedy algorithm;backtracking method;branch and bound method;time
　　背包问题（Knapsack problem）是由Merkel 和Hellman在1978年提出的，后来通过对其特点的研究，表明该问题是一个典型的NP-complete问题。它被广泛应用在各种工业场合中，如资本预算、货物装载和存储分配等问题，这些问题都可以转化成0-1背包问题，因此研究0-1背包问题的求解方法具有非常重要的现实意义[1]。
　　0-1背包问题是一个经典算法，求解的方法非常多。从不同角度思考，就有不同的算法策略。常用的策略有：动态规划法、贪心算法、回溯法和分支限界法。在实际应用中，我们应该如何决策選定哪一种策略，本文从此问题展开探索。
　　1 0-1背包问题的描述
　　文字描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量是c。问：应如何选择装入背包中的物品，使得装入背包中物品价值最大？对选入物品只有装入和不装入，不能装，人多次，也不能只装入物品的部分。
　　数学描述：给定c》0，w;》0，v;》0，1≤i≤n，要求找出一个
　　2 求绝对最优解的策略——动态规划法
　　0-1背包问题要求解的是装入背包中的物品价值最大。这是一个最优值，要解出绝对的最优解，动态规划算法是一个很好的策略。
　　2.1 动态规划法的基本思想
　　动态规划法的核心思想就是：原问题的最优值由它的最小子问题的最优值逐步扩大规模，逐一求解，即由底向上的求问题的最优值;然后根据计算最优值的过程中保留一定的辅助数据，去构建问题的最优解。
　　由动态规划法的核心思想可知，能由动态规划法求解的问题必须包含两个要素即：最优子结构性质和重叠子问题。最优子结构性质即是原问题的最优解包含了子问题的最优解。重叠子问题很好理解，即一个较小规模的子问题可以是很多比它规模较大问题的子问题，如果没有这个性质，子问题是相互独立的，我们可以采取更优的策略即分治策略求解。
　　2.2 0-1背包问题的动态规划法求解
　　1）建立数学递归关系
　　子问题的最优值构建m（i，j）：是背包容量为j，可选择物品为i，i+1，…n时背包的能装入物品价值的最大值。当求解m（i，j）时，比它小的子问题m（i+1，j）已求解得到最优值。对于当前考虑的第i个物品，就有两种情况：1）当前的背包容量j装不下物品i，这时它的最优解就等同于m（i+1，j）;2）当前的j能装下物品i，这时，我们就可以选择装入或者不装入。不装入等同于第一种情况;装入那么背包当前价值就要在前一子问题（m（i+1，j-wi））的最优值上加上第i物品的价值。所以当前容量能装下物品i，就会有两个值，我们求的是当前背包价值最大，所以选择两个值中的较大者。
　　数学递归式可表达如下：
　　2）主要算法描述
　　int jMax=min（w[n]-1，c）;//c：背包当 前容量，n：物品的总个数
　　for（int j=0;j《=jMax;j++）m[n][i]=0;
　　for（int j=w[m];j《=c;j++）m[p]Ij]=v[n];
　　for（inti=n-1 ;i》 1;i—）{
　　jMax=min（w[i]-1，c）; 　　for（intj=0;j《=jMax;j++）m[i][i]=m[i+1][i];
　　for（int j=w[i];j《=c;j++）
　　m[i]lj]=max（m[i+1]i]，m[i+1][j-w[]+v[i]）;
　　if（m[]li]==m[i+1][j]）x[i]=0;/x[i]第i个物品装还是不装的解
　　elsex[i]=1;//0-不装，1-装
　　}
　　3）算法的时间复杂度分析
　　从上述主要算法描述可看出，动态规划法的时间复杂度是O（nc）的计算时间。当背包的容量c很大时，算法的时间就较多。例如，当c》 2n时，算法的时间复杂度就变成了O（n2n）。如果当背包容量足够大的时候，我们可以放弃动态规划算法，而选择贪心算法。
　　3 求近似最优解的策略——贪心算法
　　贪心算法每次所做的选择，不是从整体最优进行考虑，而是仅考虑当前局部最优的选择。当然，我们希望能得到最优解，这时，就必须要能证明此问题具有贪心选择性质和最优子结构性质。虽然不是所有问题都可以用贪心法求得最优解，但是就很多问题，当规模足够大时，由它计算出来的结果却是最优解的很好近似解。
　　3.1 贪心算法的基本思想
　　根据所求问题，寻找一个贪心点，首先按照这个点对事物进行排序。然后一次线型时间扫描，依次选择事件，直到条件不满足，结束。
　　3.2 0-1背包问题的贪心算法求解
　　当背包和所装物品的重量不在一个重量级时，如背包容量远远大于要选择物品的重量，又或者把背包换成一辆卡车，这时贪心算法是绝好的方法。根据贪心法的基本思想，我们首先将物品按照其单位重量价值递减排序，然后按照单位重量价值由高到低逐一的选择物品并装入，直到装不下。
　　贪心算法求解0-1背包问题的主要代码如下：
　　Sort（n，v，w）;//按单位重量价值排序
　　for（inti=1;i《=n;i++）x[i]=0;
　　floatc=M;//背包容量c
　　for（i=1;i《=n;i++）{ //逐一遍历已排序的物品
　　If（w[i]》c）break;//如果当前物品装不下了，就跳出循环
　　xi]=1;//装入物品
　　c-=w[i];//求得当前背包的剩余容量
　　}
　　3.3 算法的时间复杂度分析
　　贪心算法求解问题时，排序时间复杂度是O（nlogn），贪心选择的时间耗费是0（n），所以，贪心算法求解0-1背包问题的时间复杂度是O（nlogn）。
　　4 回溯法和分支限界法
　　回溯法有“通用的解题法”之称，用它可以系统的搜索一个问题的所有解或任一解[1]。回溯法和分支限界法它们有很多相似之处，都是将问题的解空间组织成一棵树，然后遍历树。不同的是回溯法按照深度优先遍历，分支限界则按照广度优先的方式遍历。
　　4.1 回溯法和分支限界法解题通常包含以下三个步骤：
　　（1）针对所给问题，定义问题的解空间;
　　（2）确定易于搜索的解空间结构;
　　（3）以深度（广度）方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索[1]。
　　4.2 0-1背包問题的回溯法和分支限界法求解
　　回溯法和分支限界法求解0-1背包问题时，首先将解空间.组织成一满二叉树。对某一物品装可构建成左子树，解的取值为1，不装可构建成右子树，解的取值为0。所以解空间树是深度为n的满二叉树。具体求解算法以回溯法为例。
　　回溯法求解0-1背包问题的主要代码如下：
　　Backtrack （inti）//i：当前遍历树的层数
　　{ if（i》n）{ //当前节点是叶子节点，得到一个当前最优值
　　bestp=cp;
　　return ;}
　　if（cw+w[i]《=c）{ //背包当前容量能装入物品i
　　cw +=w[i];//cw：当前已装入物品的重量
　　cp+=p间];//ep：当前已装入物品的价值
　　Backtrack（i+1）;//深入递归访问左子树
　　CW-=w[i];
　　cp-=p问;}
　　If（Bound （i+1）》bestp）//如果右子树中可能存在最优解
　　Backtrack（i+1）;//则深入递归访问右子树
　　}
　　4.3 算法的时间复杂度分析
　　遍历二叉树时，最坏情况是每一个分支节点和叶子节点都要访问，物品为n时，二叉树的深度为n，节点数共2n-1个。所以最坏的情况算法的时间复杂度是0（2n）。实际上，因为在遍历树的时候，会用到剪枝函数，即减去不满足条件的和不能得到最优解的子树，从而大大缩小了访问节点的个数。有时，给出的特定实例时，回溯法和分支限界法的具体运算时间会小于动态规划算法。
　　5 如何决策0-1背包问题选择何种策略
　　“条条大道通罗马”，0-1背包问题常用求解方法就有上诉四种策略，每一种策略都各自有优缺点，怎么决策呢？总的来说当我们要求问题所有解时，可选择回溯法或者分支限界法;要求问题绝对最优值时可选择动态规划法，当然也可以用回溯法和分支限界法;如果背包容量远远高于物品重量时，我们可以用贪心法求解接近最优解的近似解。当我们面对不同问题时，就要具体问题具体分析，找到既能满足条件又能提高效率的最佳方案。
　　参考文献：
　　[1]王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2007.
　　[2]王文东，武海妮.求解0-1背包问题的算法分析[J].信息与电脑：理论版，2018（9）：68-70.
　　[3]刘朝霞.求解0-1背包问题的两种算法设计[J].阴山学刊：自然科学版，2014，28（3）：5-8.
　　[4]刘文强，周波，马海峰，等.算法分析与设计课程中0-1背包问题的探讨[J].高师理科学刊，2018，38（6）：82-85.
　　[通联编辑：代影]
转载注明来源:https://www.xzbu.com/8/view-15162614.htm