回溯法——0-1背包问题

问题描述

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

算法设计分析

从所有的物品中选取若干将它们装进背包，在满足限制条件的情况下，获得最大的收益。既然要选择一个对象的子集，解空间就应该组织成子集树结构。要设计的递归算法使用深度优先搜索子集树：

​ 对于左孩子，满足限制条件即可；对于右孩子，需要利用界定函数计算此节点的收益上限，即当前节点的收益加上还未考察的对象的收益是否超过当前最优解的收益。如果不是，则不需要搜索右子树。

下面考虑界定函数：

实例：0/1背包问题，当n=3时，w={20,15,15}, p={40,25,25}, c=30，收益密度{2, 5/3, 5/3}。

当以收益密度递减顺序装包时，首先选择对象1，此时剩余容量为10，只能装下2/3的对象2，则生成的解为{1, 2/3, 0}，总收益为170/3，虽然这个解不可行（装包量必须是0或1），但可以作为一个界定值，因为它不小于任何一个可行解包括最优解。所以，将对象按收益密度递减顺序排列，能够容易得到界定函数。

算法步骤：

1、将背包装载对象按收益密度递增顺序排序； 
2、对于当前节点currentLevel,判断是否大于对象数，若否，继续下面步骤，反之，算法终止； 
3、检查左孩子，若不超过总的容量，左孩子可行，递归左子树； 
4、检查右孩子，若有孩子的收益上限大于当前最优解的最大收益，左孩子可行，递归右子树； 
上述实例的回溯过程如图： 
A ——> B ——> E ——> B ——> A ——> C ——> F ——> L ——> F ——> C ——> A 

C++实现

定义一个结构element，其数据成员是id（对象标志符）和profitDensity。用于对对象按照收益密度进行递减排序。

struct element
{
//data members 
int id;
double profitDensity;

//constructor
  element(int theId, double theProfitDensity) : id(theId), profitDensity(theProfitDensity) { }
};
//used in sort() 
bool operator<=(const element &lhs, const element &rhs)
{
return lhs.id < rhs.id;
}

定义全部变量和knapSack函数：

//全局变量
double capacity;
int numberOfObjects;
double *weight;
double *profit;
double weightOfCurrentPacking;
double profitFromCurrentPacking;
double maxProfitSoFar;

//函数knapSack
double knapSack(double *theProfit, double *theWeight,
int theNumberOfObjects, double theCapacity)
{//theProfit[1:theNumberOfObjects]是收益
 //theWeight[1:theNumberOfObjects]是重量
 //theCapacity是背包容量
    //初始化全局变量
    capacity = theCapacity;
    numberOfObjects = theNumberOfObjects;

    weightOfCurrentPacking = 0.0;
    profitFromCurrentPacking = 0.0;
    maxProfitSoFar = 0.0;

//定义类型为element的数组，存储收益密度。q[0:n-1]
    element *q = new element[numberOfObjects];
for (int i = 1; i < numberOfObjects + 1; ++i)
q[i - 1] = element(i, theProfit[i] / theWeight[i]);

//按照收益密度递增顺序排序
sort(q, q + numberOfObjects);

//初始化剩余全局变量
    profit = new double[numberOfObjects + 1];
    weight = new double[numberOfObjects + 1];
for (int i = 1; i < numberOfObjects + 1; ++i)
    {
        profit[i] = theProfit[q[numberOfObjects - i].id];
        weight[i] = theWeight[q[numberOfObjects - i].id];
    }

    rKnap(1);
return maxProfitSoFar;
}

递归函数rKnap：

void rKnap(int currentLevel)
{//从currentLevel中的一个节点开始搜索
if (currentLevel > numberOfObjects)
    {//到达一个叶结点
        maxProfitSoFar = profitFromCurrentPacking;
return;
    }

//非叶结点，检查左孩子
if (weightOfCurrentPacking + weight[currentLevel] <= capacity)
    {//左孩子可行，搜索左子树
        weightOfCurrentPacking += weight[currentLevel];
        profitFromCurrentPacking += profit[currentLevel];
        rKnap(currentLevel + 1);
        weightOfCurrentPacking -= weight[currentLevel];
        profitFromCurrentPacking -= profit[currentLevel];
    }

//检查右孩子
if (profitBound(currentLevel + 1) > maxProfitSoFar)
//右孩子可行，搜索右子树
        rKnap(currentLevel + 1);
}

界定函数：

double profitBound(int currentLevel)
{//界定函数
//返回节点的收益上限
double remainingCapacity = capacity - weightOfCurrentPacking;
double profitBound = profitFromCurrentPacking;

//按照收益密度递减顺序填充剩余容量，计算节点收益上限
while (currentLevel <= numberOfObjects &&
        weight[currentLevel] <= remainingCapacity)
    {
        remainingCapacity -= weight[currentLevel];
        profitBound += profit[currentLevel];
        currentLevel++;
    }

//取下一个对象的一部分
if (currentLevel <= numberOfObjects)
        profitBound += remainingCapacity / weight[currentLevel] * profit[currentLevel];

return profitBound;
}

算法复杂度为Ω(2^n)。