0-1背包问题（回溯法）_01背包问题回溯法

0-1背包问题是动态规划、贪心策略的一个子问题。回溯算法同样可以适用于0-1背包问题。下面使用回溯算法解0-1背包问题。

一、问题描述

有n种物品，每种物品只有1个。 第i种物品价值为vi , 重量为wi, i=1,2,…, n。问如何选择放入背包的物品，使得总重量不超过B, 而价值达到最大？

思路：有n种物品，每个物品只有1个，放入背包可以有选择的，也可以不放。每种物品有两种选择，暴力破解就是这个样子，把所有可能的组合全部拿出来，观察能放进去的组合里面的最大的价值，那就是找到的解。如果把这个问题变成一个搜索树，也可以解的，其实相当于找一个向量。

二、算法设计

这个物品到底放不放进去的问题，找出这个向量是和这个物品的个数是有关系的，物品有n个，每个物品是放或者不放。这是一个搜索的二叉树，称之为子集树

三、实例

1、输入：

V={12,11,9,8}, W={8,6,4,3}, B=13

2、2个可行解：

<0,1,1,1>, 选入物品2,3,4，价值为28，
重量为13
<1,0,1,0>，选入物品1,3，价值为21，
重量为12

3、最优解：<0,1,1,1>

四、搜索空间

1、子集树的运行

最开始对于第1个物品而言，放或者不放。接下来在考虑对第二个物品而言，放或者不放。所以子集数会有物品数+1层，路径左边是装这个物品，路径右边是不装这个物品。

2、实例:V={12,11,9,8}, W={8,6,4,3}, B=13

3、搜索空间：子集树，2^n片树叶

第一层是第一个物品，第二层是第二个物品……每个物品占一层。采用装与不装进去到达叶结点。

4、可行解

例如装第1个物品，不装第2个物品，装第3个物品，不装第4个物品。这个路径就是<1,0,1,0>，这个路径是能装进去的，而且得到一个没有超过背包的容量能够把物品装进去的可行解，但是不一定是最优的。子集树中的虚线表示空，不再搜索。

<1,0,1,0>这个路径，第1个物品已经装进去了，重量是8，那么剩下的（13-8=7）。第2个物品是6，只有不装不然无法再装其他物品了。选择装第3个物品，剩余的空间是1（13-8-4=1），第4个物品是3，所以最后只装了第1个物品和第3个物品，并且重量还有剩余。

5、最优解

另外一条路径，不装第1个物品，装第2个物品，装第3个物品，装第4个物品。这个路径就是<0,1,1,1>，这个价值加起来是最大的。

五、代码实现

#include <iostream>
using namespace std;

#define N 5   //默认有4个物品。第一个不使用
int w[N];    //每个物品的重量
int v[N];    //每个物品的价值
int x[N];     //x[i]=1：物品i放入背包，0代表不放入
int n,c;       //n：一共有多少物品，c：背包的最大容量

int SumWeight = 0;  //当前放入背包的物品总重量
int SumValue = 0;   //当前放入背包的物品总价值

int OptimalValue = 0;  //最优价值；当前的最大价值，初始化为0
int OptimalSolution[N];       //最优解；OptimalSolution[i]=1代表物品i放入背包，0代表不放入

/*
*回溯算法 参数t表示当前处在第几层做抉择，t=1时表示当前在决定是否将第一个物品放入背包
*/
void backtracking(int t)
{
    //叶子节点，输出结果
    if(t>n)
    {
        //如果找到了一个更优的解
        if(SumValue>OptimalValue)
        {
            //保存更优的值和解
            OptimalValue = SumValue;
            for(int i=1; i<=n; ++i)
                OptimalSolution[i] = x[i];
        }
    }
    else
    {
        //遍历当前节点的子节点：0 不放入背包，1放入背包
        for(int i=0; i<=1; ++i)
        {
            x[t]=i;

            if(i==0) //不放入背包
            {
                backtracking(t+1);
            }
            else //放入背包
            {
                //约束条件：当前物品是否放的下
                if((SumWeight+w[t])<=c)
                {
                    SumWeight += w[t];
                    SumValue += v[t];
                    backtracking(t+1);
                    SumWeight -= w[t];
                    SumValue -= v[t];
                }
            }
        }
    }
}

int main()
{

    cout<<"请输入物品的个数："<<endl;
    cin>>n;
    cout<<"请输入每个物品的重量及价值(如5 4):"<<endl;
    for(int i = 1; i <= n; i++)
    {
        cin>>w[i]>>v[i];
    }
    cout<<"请输入背包的限制容量："<<endl;
    cin>>c;

    backtracking(1);

    cout<<"最优价值是:"<<OptimalValue<<endl;
    cout<<"(";
    for(int i=1;i<=n;i++)
        cout<<OptimalSolution[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
76
77
78
79
80
81