背包问题系列算法详解

背包问题系列算法详解背包问题是一个关于最优解的经典问题。通常被讨论的最多的，最经典的背包问题是0-1背包问题(0-1KnapsackProblem)。它是一切背包问题及相关背包问题的基础。本篇博文将详细分析0-1背包问题，并给出0-1背包问题的几种解法，同时也对0-1背包问题的内涵进行延伸，丰富其外延至完全背包问题和多重背包问题，并给出背包问题的算法实现过程，希望对大家有帮助。一、0-1背包问题有N件物品和一个容量为V的背包。第i件物品（每个物品只有一件）的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。（1）递归求解算法如下：#includeiostream#defineCAPACITY10#defineGOODSNUM6usingnamespacestd;intnVol[GOODSNUM];intnValue[GOODSNUM];intknapsack(intitemIndex,intvol);voidmain(){inti=0,j=0;while(iGOODSNUM){coutinputthei+1thitem(volumeandvalue):;cinnVol[i]nValue[i];i++;}coutThemaxvalueis:knapsack(GOODSNUM,CAPACITY)endl;}intknapsack(intitemIndex,intvol){if(itemIndex==0||vol==0){return0;}elseif(vol=nVol[itemIndex]&&knapsack(itemIndex-1,vol)knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex]){returnknapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex];}elsereturnknapsack(itemIndex-1,vol);}分析：递归求解，求解过程中的绝大部分变量存在重复求解的过程，算法的效率较低，有待改进；那怎么改进呢？最有效的是用数组保存每次计算的结果，不用重复计算，于是有二维数组求解。（2）二维数组求解算法如下：#includeiostream#defineCAPACITY10#defineGOODSNUM6usingnamespacestd;voidmain(){inti=1,j;intv[GOODSNUM]={10,12,40,40,40,15};intc[GOODSNUM]={1,2,3,5,2,1};intfun[GOODSNUM+1][CAPACITY+1];for(i=1;i=GOODSNUM;i++){fun[i][0]=0;}for(i=1;i=CAPACITY;i++){fun[0][i]=0;}for(i=1;i=GOODSNUM;i++){for(j=1;j=CAPACITY;j++){if(jc[i-1]){fun[i][j]=fun[i-1][j];}elseif(fun[i-1][j]fun[i-1][j-c[i-1]]+v[i-1]){fun[i][j]=fun[i-1][j-c[i-1]]+v[i-1];}elsefun[i][j]=fun[i-1][j];}}coutThemaxvalueis:fun[GOODSNUM][CAPACITY]endl;}分析：二维数组求解方法相比递归求解要优越很多，但是其空间复杂度依然较高，还有继续改进的余地吗？一维数组是否可行呢？答案是肯定的（3）一维数组求解算法分析：#includeiostream#defineCAPACITY10#defineGOODSNUM6usingnamespacestd;voidmain(){intnVolume[GOODSNUM]={1,2,3,5,2,1};intnValue[GOODSNUM]={10,12,40,40,40,15};intselectTable[GOODSNUM][CAPACITY+1]={0};intnKnapsack[CAPACITY+1]={0};//mostimportantforthefirstcomputionbelowintitemIndex,capIndex;for(itemIndex=0;itemIndexGOODSNUM;itemIndex++){for(capIndex=CAPACITY;capIndex=nVolume[itemIndex];capIndex--)//noticethatcapIndex=nVolume[itemIndex],notcapIndex=0注意此处与二维数组求解的区别{if(nKnapsack[capIndex]nKnapsack[capIndex-nVolume[itemIndex]]+nValue[itemIndex]){nKnapsack[capIndex]=nKnapsack[capIndex-nVolume[itemIndex]]+nValue[itemIndex];selectTable[itemIndex][capIndex]=1;}elsenKnapsack[capIndex]=nKnapsack[capIndex];}}coutThemaxvalueis:nKnapsack[CAPACITY]endl;coutTheselecteditemsare:;for(itemIndex=GOODSNUM-1,capIndex=CAPACITY;itemIndex=0;itemIndex--){if(selectTable[itemIndex][capIndex]){coutitemIndex+1;capIndex=capIndex-nVolume[itemIndex];}}coutendl;}分析：在一维数组实现中将空间复杂度由O(GOODSNUM*CAPACITY)降低到O(CAPACITY)并同时进行了代码优化，同时也给出了选择物品的编号。二、完全背包问题若你能给深入理解0-1背包问题和其深刻内涵，并真正明白一维数组求解背包问题后，下面的问题对你来说就相当容易了。完全背包问题：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。求解分析：目标是转化为0-1背包问题。如将费用/容量为nVolume[itemIndex]的物品转化为CAPACITY/nVolume[itemIndex]相同费用和价值的物品，直接用前面的三种0-1背包问题求解。除此之外还有其它可行的求解方法吗？可以对0-1背包问题的状态方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}稍加分析可得完全背包问题的状态方程f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0=k*c[i]=v}，因而有以下算法实现过程，并最终给出了所选择的物品和选择该物品的数目。实现算法：#includeiostream#defineCAPACITY10#defineGOODSNUM6usingnamespacestd;voidmain(){intnum,k,max;intnVolume[GOODSNUM]={1,4,3,5,5,3};intnValue[GOODSNUM]={2,8,40,60,10,3};intselectTable[GOODSNUM][CAPACITY+1]={0};intnKnapsack[CAPACITY+1]={0};//mostimportantforthefirstcomputionbelowintitemIndex,capIndex;for(itemIndex=0;itemIndexGOODSNUM;itemIndex++){for(capIndex=CAPACITY;capIndex=nVolume[itemIndex];capIndex--)//noticethatcapIndex=nVolume[itemIndex],notcapIndex=0{num=0;max=nKnapsack[capIndex];for(k=1;k=CAPACITY/nVolume[itemIndex];k++){if(capIndex=k*nVolume[itemIndex]&&maxnKnapsack[capIndex-k*nVolume[itemIndex]]+k*nValue[itemIndex]){max=nKnapsack[capIndex-k*nVolume[itemIndex]]+k*nValue[itemIndex];num=k;}}nKnapsack[capIndex]=max;selectTable[itemIndex][capIndex]=num;}}coutThemaxvalueis:nKnapsack[CAPACITY]endl;coutTheselecteditemsare:endl;for(itemIndex=GOODSNUM-1,capIndex=CAPACITY;itemIndex=0;itemIndex--){if(selectTable[itemIndex][capIndex]){coutitemIndex+1:selectTable[itemIndex][capIndex];capIndex=capIndex-selectTable[itemIndex][capIndex]*nVolume[itemIndex];}}coutendl;}三、多重背包问题多重背包问题：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。多重背包问题基本求解方式同完全背包问题，唯一的是控制参数k的限制有所不同。只需要将完全背包问题实现中的k=CAPACITY/nVolume[itemIndex]限制条件改为k=CAPACITY/nVolume[itemIndex]&&k=n[i]即可。