背包问题系列详解

背包问题是一个关于最优解的经典问题。通常被讨论的最多的，最经典的背包问题是0-1背包问题(0-1 Knapsack Problem)。它是一切背包问题及相关背包问题的基础。本篇博文将详细分析0-1背包问题，并给出0-1背包问题的几种解法，同时也对0-1背包问题的内涵进行延伸，丰富其外延至完全背包问题和多重背包问题，并给出背包问题的算法实现过程，希望对大家有帮助。

一、0-1背包问题

有N件物品和一个容量为V的背包。第i件物品（每个物品只有一件）的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品。因此，该问题称为0-1背包问题。

（1）递归求解

算法如下：

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6
using namespace std;
int nVol[GOODSNUM];
int nValue[GOODSNUM];


int knapsack(int itemIndex,int vol);


void main()
{
 int i=0,j=0;
 while(i<GOODSNUM)
 {
  cout<<"input the "<<i+1<<"th item(volume and value):";
  cin>>nVol[i]>>nValue[i];
  i++;
 }
 cout<<"The max value is: "<<knapsack(GOODSNUM,CAPACITY)<<endl;
}


int knapsack(int itemIndex,int vol)
{
 if (itemIndex==0||vol==0)
 {
  return 0;
 }
 else if (vol>=nVol[itemIndex] && knapsack(itemIndex-1,vol)<knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex])
  {
   return knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex];
  }
 else 
  return knapsack(itemIndex-1,vol);
}

分析：递归求解，求解过程中的绝大部分变量存在重复求解的过程，算法的效率较低，有待改进；那怎么改进呢？最有效的是用数组保存每次计算的结果，不用重复计算，于是有二维数组求解。

（2）二维数组求解

算法如下：

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6


using namespace std;


void main()
{
 int i=1,j;
 int v[GOODSNUM] = {10,12,40,40,40,15};
 int c[GOODSNUM] = {1,2,3,5,2,1};
 int fun[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 (j<c[i-1])
   {
    fun[i][j] = fun[i-1][j];
   }
   else if (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];
    }
   else
    fun[i][j] = fun[i-1][j];
  }
 }
 cout<<"The max value is: "<<fun[GOODSNUM][CAPACITY]<<endl;
}

分析：二维数组求解方法相比递归求解要优越很多，但是其空间复杂度依然较高，还有继续改进的余地吗？一维数组是否可行呢？答案是肯定的

（3）一维数组求解

算法分析：

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6


using namespace std;


void main()
{
 int nVolume[GOODSNUM] = {1,2,3,5,2,1};
 int nValue[GOODSNUM] = {10,12,40,40,40,15};
 int selectTable[GOODSNUM][CAPACITY+1] = {0};
 int nKnapsack[CAPACITY+1] = {0};//most important for the first compution below
 int itemIndex,capIndex;
 for (itemIndex=0;itemIndex<GOODSNUM;itemIndex++)
 {
  for (capIndex=CAPACITY;capIndex>=nVolume[itemIndex];capIndex--)//notice that capIndex>=nVolume[itemIndex],not capIndex>=0  注意此处与二维数组求解的区别
  {
   if (nKnapsack[capIndex]<nKnapsack[capIndex-nVolume[itemIndex]]+nValue[itemIndex])
   {
    nKnapsack[capIndex] = nKnapsack[capIndex-nVolume[itemIndex]]+nValue[itemIndex];
    selectTable[itemIndex][capIndex] = 1;
   }
   else
    nKnapsack[capIndex] = nKnapsack[capIndex];
  }
 }
 cout<<"The max value is: "<<nKnapsack[CAPACITY]<<endl;
 cout<<"The selected items are: ";
 for (itemIndex = GOODSNUM-1,capIndex = CAPACITY;itemIndex>=0;itemIndex--)
 {
  if (selectTable[itemIndex][capIndex])
  {
   cout<<itemIndex+1<<" ";
   capIndex = capIndex - nVolume[itemIndex];
  }
 }
 cout<<endl;
}

分析：在一维数组实现中将空间复杂度由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}，因而有以下算法实现过程，并最终给出了所选择的物品和选择该物品的数目。

实现算法：

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6


using namespace std;


void main()
{
 int num,k,max;
 int nVolume[GOODSNUM] = {1,4,3,5,5,3};
 int nValue[GOODSNUM] = {2,8,40,60,10,3};
 int selectTable[GOODSNUM][CAPACITY+1] = {0};
 int nKnapsack[CAPACITY+1] = {0};//most important for the first compution below
 int itemIndex,capIndex;
 for (itemIndex=0;itemIndex<GOODSNUM;itemIndex++)
 {
  for (capIndex=CAPACITY;capIndex>=nVolume[itemIndex];capIndex--)//notice that capIndex>=nVolume[itemIndex],not capIndex>=0
  {
   num = 0;
   max = nKnapsack[capIndex];
   for (k=1;k<=CAPACITY/nVolume[itemIndex];k++)
   {
    if (capIndex>=k*nVolume[itemIndex] && max<nKnapsack[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;
  }
 }
 cout<<"The max value is: "<<nKnapsack[CAPACITY]<<endl;
 cout<<"The selected items are: "<<endl;
 for (itemIndex = GOODSNUM-1,capIndex = CAPACITY;itemIndex>=0;itemIndex--)
 {
  if (selectTable[itemIndex][capIndex])
  {
   cout<<itemIndex+1<<":"<<selectTable[itemIndex][capIndex]<<" ";
   capIndex = capIndex - selectTable[itemIndex][capIndex]*nVolume[itemIndex];
  }
 }
 cout<<endl;
}

三、多重背包问题

多重背包问题：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

多重背包问题基本求解方式同完全背包问题，唯一的是控制参数k的限制有所不同。只需要将完全背包问题实现中的

k<=CAPACITY/nVolume[itemIndex]

限制条件改为

k<=CAPACITY/nVolume[itemIndex] && k<= n[i]

即可。