0-1背包问题 - 回溯法 - 深度搜索

算法描述：

0-1背包问题是子集选取问题。一般情况下，0-1背包问题是NP难得。0-1背包问题的解空间可用子集树 表示。在搜索解空间的时，只要其左儿子节点是一个可行节点，搜索就进去其左子树(约束条件)。当右子树中可能包含最优解时才进入右子树搜索(限界函数)。否则就将右子树剪去。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入物品的一部分而装满背包。由此得到的价值是右子树中解的上界。

例如，对于0-1背包问题的一个实例，n = 4, c = 7, p = [9, 10, 7, 4], w = [3, 5, 2, 1]。 这四个物品的单位重量分别是[3, 2, 3, 5, 4]。依物品单位重量价值递减序装入物品。先装入物品4，然后装入物品3 和 1。装入这三个物品后，剩余的背包容量为1，只能装入物品2的五分之一( 2 * 五分之一 = 1)。由此得到的一个解为x = [1, 0.2(五分之一), 1, 1]， 其响应的的价值是22。尽管这不是一个可行解，但可以证明其价值是最优值的上界(限界函数)。因此，对于这个实例，最优值不超过22。

为了计算上界，可先将物品将其单位重量价值从大到小排序。此后只要按照顺序考察个物品即可。Bound()函数为限界函数。

from 计算机算法设计与分析(第四版) 王晓东编著

另外由于排了序，物品的代号改变，无法输出得到最优解时装入了哪些物品。不过可以创建一个类定义属性 id 来实现记录。这个算法中已实现。

算法实现：

#include <bits/stdc++.h>
using namespace std;
class Object
{
public:
    int p;
    int w;
    int id;
};
int n, c, cp, cw, bestp, total_w, total_p;
int x[100], best_x[100];
Object O[100];
void Input()
{
    scanf("%d %d", &n, &c);
    for(int i = 1; i <= n; ++i)
    {
     scanf("%d %d", &O[i].p, &O[i].w);
     O[i].id = i;
    }
}
bool cmp(const Object &a, const Object &b)
{
    return a.p / a.w > b.p / b.w;
}
void Initilize()
{
    cp = cw = total_w = total_p = bestp = 0;
    for(int i = 1; i <= n; ++i)
    {
        total_p += O[i].p;
        total_w = O[i].w;
    }
    //依照物品单位重量价值排序
    sort(O + 1, O + n + 1, cmp);
    //for(int i = 1; i <= n; ++i)
        //cout << O[i].id << endl;
}
int Bound(int i)
{
    int temp_cw = c - cw;
    int temp_cp = cp;
    while(i <= n && temp_cw >= O[i].w)
    {
        temp_cw -= O[i].w;
        temp_cp += O[i].p;
        ++i;
    }
    //装满背包
    if(i <= n)
        temp_cp += O[i].p / O[i].w * temp_cw;
    return temp_cp;


}
void Backtrack(int i)
{
    if(i > n)
    {
        bestp = cp;
        for(int i = 1; i <= n; ++i)
            best_x[i] = x[i];
        return;
    }
    if(cw + O[i].w <= c)
    {
        x[O[i].id] = 1;
        cw += O[i].w;
        cp += O[i].p;
        Backtrack(i + 1);
        cp -= O[i].p;
        cw -= O[i].w;
        x[O[i].id] = 0;
    }
    if(Bound(i + 1) > bestp)
    {
        x[O[i].id] = 0;
        Backtrack(i + 1);
    }
}
void OutPut()
{
    printf("bestp = %d\n", bestp);
    printf("选取的物品为 : \n");
    for(int i = 1; i <= n; ++i)
    {
        if(best_x[i] == 1)
           cout << i << " ";
    }
}
int main()
{
    Input();
    Initilize();
    Backtrack(1);
    OutPut();
}

测试样例：

输入：

4 7
9 3
10 5
7 2
4 1

输出

bestp = 20

所选物品为：

1 3 4

截图：