背包问题系列算法详解

1、背包问题系列算法详解 背包问题是一个关于最优解的经典问题。通常被讨论的最多的，最经典的背包问题是0-1背包问题(0-1 Knapsack Problem)。它是一切背包问题及相关背包问题的基础。本篇博文将详细分析0-1背包问题，并给出0-1背包问题的几种解法，同时也对0-1背包问题 的内涵进行延伸，丰富其外延至完全背包问题和多重背包问题，并给出背包问题的算法实现过程，希望对大家有帮助。一、0-1背包问题 有N件物品和一个容量为V的背包。第i件物品（每个物品只有一件）的费用是ci，价值是wi。求解将哪些物品装入背包可使价值总和最大。（1）递归求解算法如下：#include iostream#de

2、fine CAPACITY 10#define GOODSNUM 6using namespace std;int nVolGOODSNUM;int nValueGOODSNUM;int knapsack(int itemIndex,int vol);void main()int i=0,j=0;while(iGOODSNUM)coutinput the i+1nVolinValuei;i+;coutThe max value is: knapsack(GOODSNUM,CAPACITY)=nVolitemIndex & knapsack(itemIndex-1,vol)knapsack(it

3、emIndex-1,vol-nVolitemIndex)+nValueitemIndex)return knapsack(itemIndex-1,vol-nVolitemIndex)+nValueitemIndex;else return knapsack(itemIndex-1,vol); 分析：递归求解，求解过程中的绝大部分变量存在重复求解的过程，算法的效率较低，有待改进；那怎么改进呢？最有效的是用数组保存每次计算的结果，不用重复 计算，于是有二维数组求解。（2）二维数组求解算法如下：#include iostream#define CAPACITY 10#define GOODSNUM

4、6using namespace std;void main()int i=1,j;int vGOODSNUM = 10,12,40,40,40,15;int cGOODSNUM = 1,2,3,5,2,1;int funGOODSNUM+1CAPACITY+1;for (i=1;i=GOODSNUM;i+)funi0 = 0;for (i=1;i=CAPACITY;i+)fun0i = 0;for (i=1;i=GOODSNUM;i+)for (j=1;j=CAPACITY;j+)if (jci-1)funij = funi-1j;else if (funi-1jfuni-1j-ci-1 +

5、 vi-1)funij = funi-1j-ci-1 + vi-1;elsefunij = funi-1j;coutThe max value is: funGOODSNUMCAPACITYendl; 分析：二维数组求解方法相比递归求解要优越很多，但是其空间复杂度依然较高，还有继续改进的余地吗？一维数组是否可行呢？答案是肯定的（3）一维数组求解算法分析：#include iostream#define CAPACITY 10#define GOODSNUM 6using namespace std;void main()int nVolumeGOODSNUM = 1,2,3,5,2,1;int

6、 nValueGOODSNUM = 10,12,40,40,40,15;int selectTableGOODSNUMCAPACITY+1 = 0;int nKnapsackCAPACITY+1 = 0;/most important for the first compution belowint itemIndex,capIndex;for (itemIndex=0;itemIndex=nVolumeitemIndex;capIndex-)/notice that capIndex=nVolumeitemIndex,not capIndex=0 注意此处与二维数组求解的区别if (nKna

7、psackcapIndexnKnapsackcapIndex-nVolumeitemIndex+nValueitemIndex)nKnapsackcapIndex = nKnapsackcapIndex-nVolumeitemIndex+nValueitemIndex;selectTableitemIndexcapIndex = 1;elsenKnapsackcapIndex = nKnapsackcapIndex;coutThe max value is: nKnapsackCAPACITYendl;cout=0;itemIndex-)if (selectTableitemIndexcapI

8、ndex)coutitemIndex+1 ;capIndex = capIndex - nVolumeitemIndex;coutendl; 分析：在一维数组实现中将空间复杂度由O(GOODSNUM*CAPACITY)降低到O(CAPACITY)并同时进行了代码优化，同时也给出了选择物 品的编号。二、完全背包问题 若你能给深入理解0-1背包问题和其深刻内涵，并真正明白一维数组求解背包问题后，下面的问题对你来说就相当容易了。 完全背包问题：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是ci，价值是wi。求解将哪些物品装入背包可使这些 物品的费用总和不超过背包容量，且价

9、值总和最大。 求解分析：目标是转化为0-1背包问题。如将费用/容量为nVolumeitemIndex的物品转化为CAPACITY /nVolumeitemIndex相同费用和价值的物品，直接用前面的三种0-1背包问题求解。除此之外还有其它可行的求解方法吗？可以对0-1背 包问题的状态方程fiv=maxfi-1v,fi-1v-ci+wi稍加分析可得完全背包问题的状态方程fi v=maxfi-1v-k*ci+k*wi|0=k*ci=v，因而有以下算法实现过程，并最终给出了所选 择的物品和选择该物品的数目。 实现算法：#include iostream#define CAPACITY 10#defi

10、ne GOODSNUM 6using namespace std;void main()int num,k,max;int nVolumeGOODSNUM = 1,4,3,5,5,3;int nValueGOODSNUM = 2,8,40,60,10,3;int selectTableGOODSNUMCAPACITY+1 = 0;int nKnapsackCAPACITY+1 = 0;/most important for the first compution belowint itemIndex,capIndex;for (itemIndex=0;itemIndex=nVolumeitem

11、Index;capIndex-)/notice that capIndex=nVolumeitemIndex,not capIndex=0num = 0;max = nKnapsackcapIndex;for (k=1;k=k*nVolumeitemIndex & maxnKnapsackcapIndex-k*nVolumeitemIndex+k*nValueitemIndex)max = nKnapsackcapIndex-k*nVolumeitemIndex+k*nValueitemIndex;num = k;nKnapsackcapIndex = max;selectTableitemIndexcapIndex = num;coutThe max value is: nKnapsackCAPACITYendl;coutThe selected items are: =0;itemIndex-)if (selectTableitemIndexcapIndex)coutitemIndex+1:selectTableitemIndexcapIndex ;capIndex = capIndex - selectTableitemIndexcapIndex*nVolumeitemIndex;coutendl;三、多重背包问题 多重背包问题：有N种物品和一个容量为V的背包。第i