背包问题-回溯法

0-1背包问题是子集选取问题。

一般情况下，0-1背包问题是NP完全问题。0-1背包问题的解空间可以用子集树表示。解0-1背包问题的回溯法与解装载问题的回溯法十分相似。在搜索解空间树时，只要其左儿子节点是一个可行的节点，搜索就进入其左子树;而当右子树中有可能包含最优解时才进入右子树搜索，否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r<=bestp时，可剪去右子树。计算右子树中解的上界的更好的办法是，将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，由此得到的价值是右子树的上界。

0–1背包的一个实例：n=5, c=10, w={2, 2, 6, 5, 4}, v(p)={6, 3, 5, 4, 6}的0-1背包问题的最优解和最优值。<w为重量，v为价值量，n为物品个数，c为背包容量>

回溯法基本思想

确定了解空间的组织结构后，【回溯法从开始节点（根节点）出发，以深度优先搜索整个解空间。这个开始的节点为活节点，同时成为当前的扩展节点。在当前的扩展节点处，搜素向纵深方向移至一个新节点。这个新节点就成为新的活节点，并成为当前扩展节点。如果当前节点处不能再向纵深方向移动，则当前扩展节点为死节点。此时，应往回移动到最近的一个活节点处。回溯法以这种方式递归的在解空间中搜素，直至找到所有符合要求的解或解空间中已无活节点。】（即深度优先搜素）

回溯法的典型实例——0-1背包问题
为了方便理解回溯法运算的流程，以0-1背包问题为例进行分析；

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

首先考虑贪心法，为了得到最大的价值，将所有物品按照单位价值（Vi/Wi）降序排列（例如采用希尔排序，时间复杂度为），在放入物品时优先考虑单位价值更高的物品。在搜索到空间树中的某个结点P时，已经确定了P及其前面的结点取值，进而判断从P继续扩展下去是否获得更大的价值，如果不能，该结点无需扩展，可以进行回溯了。下面的函数结合了贪心法判断从某一点扩展开去可能获得的最大的价值。

int Bound(int *Values, int *Weights,int n,int maxWeight,int num,int current_Weight,int current_profit)
{
    int i = num + 1;
    for (; i < n; i++)
    {
        if (current_Weight + Weights[i] < maxWeight)
        {
            current_profit += Values[i];
            current_Weight += Weights[i];
        }
        else
        {
            current_profit += (Values[i] / Weights[i])*(maxWeight - current_Weight);
            current_Weight = maxWeight;
            return current_profit;
        }
    }
 
    return current_profit;
}
int *Knapsack(int *Values,int *Weights,int n,int maxWeight)
{
    int *X = new int[n];
    int *Y = new int[n];
    int Weight = 0;
    int Profit = 0;
 
    int current_weight=0, current_profit=0;
 
    int i = 0;
    while (1)
    {
        while (i<n&&t_weight + Weights[i] <= maxWeight)
        {
            X[i] = SELECT;
            current_profit += Values[i];
            current_weight += Weights[i];
            i++;
        }
        //---上面的循环中，如果是由于i=n结束的，那么说明深度搜索已经搜索到了最底层
        if (i >= n)
        {
            Weight = current_weight;
            Profit = current_profit;
            i = n;
            for (int j = 0; j < n; j++)                 //------------把数组X挪给Y；
            {
                Y[j] = X[j];
            }
        }
        //否则就是由于第i个物品在当前情况下无法放入背包
        else
        {
            X[i] = UNSELECT;
        }
 
        
        while (Bound(Values, Weights, n, maxWeight, i, current_weight, current_profit) <= Profit)//如果不可能获得更大的价值，那么这个点就不需要进行扩展了；
        {
            while (i != 0 && X[i] != SELECT)//进行回溯
            {
                i--;
            }
            if (i == 0)   //当回溯到i=0时候，所有情况都遍历了
            {
                return Y;
            }
 
            X[i] = UNSELECT;
            current_profit -= Values[i];
            current_weight -= Weights[i];
        }
        i++;
    }
    
}