计算机算法分析与设计（20）---回溯法(0-1背包问题)

---

1. 题目描述

 对于给定的 $n$ 个物品，第 $i$ 个物品的重量为 $W_i$，价值为 $V_i$，对于一个最多能装重量 $c$ 的背包，应该如何选择放入包中的物品，使得包中物品的总价值最大？

2. 算法思路

 1. 将问题转化为：

 2. 按照上述思路，先将各物品按照单位价值递减的顺序排序，其次进行判断是否在承重范围值内。
 定义：$cw$（current weight）表示当前重量，$cp$（current price）表示当前价值。
 根节点代表扩展结点 ，其余每一层代表一个物品，越靠近根节点，单位价值越高。选中该物品，即搜索左子树，进行判断。具体执行操作如下所示：

 （1）先计算所有物品的单位价值，将其进行降序排列。

 （2）排列之后，从根节点(扩展节点)出发。

 （3）搜索左子树，判断是否满足约束条件(物品是否装入背包)：

       若选中该物品（可行解），cw+=w[i]，cp+=p[i]，继续向下遍历；

       直至遇到不可行解时，开始向上回溯，取出最后一个装入的物品，进入右子树。
1
2
3

 （4）进入右子树，首先计算当前节点的上界bound(i)：

       若bound(i)小于bestp，剪去右子树，继续向上回溯；
       
       否则进行步骤（3）。
1
2
3

 （5）遇到叶子节点，比较当前价值与bestp，若cp>bestp，则bestp进行更新。

 （6）直到遍历完所有的节点（除剪枝部分外）。

3. 例题分析

 1. 例题1(手写)：

注意：这里 $ub$ 其实是松弛了一些，好好理解一下，因为是按照单位重量价值递减排序的！
虽然上面这样定义，但下面这个题算 $ub$ 我们还是正常算。

 2. 例题2：假设 $n=3$（有三件物品），三个物品的重量为 $20、15、10$，三个物品的价值为 $20、30、25$，对于一个最大承重为 $25$ 的背包，求包中物品的组合最大的价值是多少？

 3. 例题2分析过程：对三件物品分别进行编号 $1，2，3$。初始情况背包是空的。

 （1）首先我们把 $1$ 号物品放进背包里，此时背包里只有一件物品，总重量为 $0+20=20$，没有超过承重 $25$，因此可以将 $1$ 号物品成功放入背包内。

 （2）接下来尝试把 $2$ 号物品放入背包内，但是发现包中 $1$ 号物品和 $2$ 号物品的重量和为 $20+15=35$，超过了承重 $25$，因此不能把 $2$ 号物品放入背包内。

 （3）接着考虑 $3$ 号物品，此时包中只有 $1$ 号物品。发现 $1$ 号物品和 $3$ 号物品的重量和为 $20+10=30$，超过了承重 $25$，因此 $3$ 号物品也不能放入背包内。

 （4）由于只有 $3$ 件物品，并且对于每一种物品我们都考虑过是否将其放入背包内，也就是找到了一种基本情况。找到一个基本情况后，我们就可以看看包里的物品的总价值了。这里包里只有一个 $1$ 号物品，因此总价值为 $20$。

 （5）重点来了！回溯过程：每次找出一种满足条件的基本情况就进行一次回溯，找到最后放入包中的物品并将其取出，接着考虑是否放入编号在这个物品之后的第一个物品。这里我们就把 $1$ 号物品取出，接下来考虑是否放入 $2$ 号物品。

 （6）取出 $1$ 号物品后背包是空的，此时如果放入 $2$ 号物品，背包总重量为 $15$，没有超过背包承重，因此把 $2$ 号物品放入背包内。

 （7）类似地，考虑将 $3$ 号物品放入背包内。由于 $2$ 号物品和 $3$ 号物品的重量和为 $15+10=25$，没有超过承重 $25$，因此将其放入背包内。

 （8）由于考虑完了 $3$ 号物品，因此又找到了一个基本情况，记下此时包里物品的总价值，为 $30+25=55$。由于 $55$ 高于上一种基本情况的总价值，因此将最优解更新为 $55$。

 （9）进行一次回溯，取出背包中最后放入的物品，也就是 $3$ 号物品。但是注意：当最后放入背包中的物品恰好是编号最大的物品时，需要额外进行一次回溯。为什么呢？因为编号最大的物品之后已经没有编号更大的物品了，因此没有可以考虑的下一种情况，只能在上一个层面上在进行一次回溯才能产生可能的最优解（此处不必考虑只放入2号物品的情况，因为一定不是最优解，原因可以自己思考一下）。 这里再回溯一次，也就是将倒数第二个放入包中的物品取出来，这里就取出 $2$ 号物品。先后取出 $3$ 号物品和 $2$ 号物品之后包应该处于空的状态。

 （10）上一步中取出了 $2$ 号物品，因此这一步直接考虑能否放入$3$ 号物品，简单的判断后即可得出可以放入，并且同上理也可以得出这是一种基本情况。但是由于包中只有 $3$ 号物品，总价值为 $25$，没有超过当前的最优解 $55$，因此将该情况忽略。

 （11）最后一次回溯，取出包中的 $3$ 号元素。由于此时包已经空了，并且最后一次取出的是编号最大的元素，那么说明算法已经完成了所有情况的遍历，算法终止，$55$ 是最优解。

4. 代码编写

// n=5, c=10, w={2, 2, 6, 5, 4}, v={6, 3, 5, 4, 6}的0-1背包问题的最优解和最优值。
#include 
using namespace std;
 
#define N 10
int w[N]; //重量
int v[N]; //价值
int x[N]; //1表放入背包，0表不放入
int n,c;  //n：物品个数 c：背包的最大容量
 
int cw=0; //当前物品总重
int cv=0; //当前物品总价值
 
int bestp=0;  //当前最大价值
int bestx[N]; //最优解
 
//回溯函数 k表示当前处在第几层做选择，k=1时表示决定是否将第一个物品放入背包
void backtrack(int k)
{//叶子节点，输出结果
   if(k>n)
   {
   //找到一个更优的解
     if(cv>bestp)
	 {  //保存更优的值和解
        bestp = cv;
        for(int i=1; i<=n; i++)
            bestx[i] = x[i];
     }
    }
   else
   {//遍历当前节点的子节点
     for(int i=0; i<=1; i++)
	 {
        x[k]=i;
        if(i==0)
		{
            backtrack(k+1);
        }
        else
		{  //约束条件：当前物品是否放的下
           if((cw+w[k])<=c)
		   {
             cw += w[k];
             cv += v[k];
             backtrack(k+1);
             cw -= w[k];
             cv -= v[k];
           }
        }
     }
  }
}
 
int main()
{
 
    cout<<"请输入物品的个数：";
    cin>>n;
    cout<<"请输入每个物品的重量及价值:"<<endl;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
    }
    cout<<"请输入背包的限制容量：";
    cin>>c;
    backtrack(1);
    cout<<"最优值是:"<<bestp<<endl;
    cout<<"(";
    for(int i=1;i<=n;i++)
    {
    	cout<<bestx[i]<<" ";
	} 
    cout<<")";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75