回溯算法--01背包问题

朴灿烈づ我的快乐病毒、 2024-03-24 15:14 54阅读 0赞

**目录**

回溯算法--01背包问题

\[算法描述\]

\[回溯法基本思想\]

法一：

法二：

代码：

运行结果

代码改进

--------------------

## 回溯算法--01背包问题 ##

### **\[算法描述\]** ###

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

0--1背包的一个实例：

n=3, c=50,

w=\{10，30，20\},

v(p)=\{60，120，100\}的

0-1背包问题的最优解和最优值。<w为重量，v为价值量，n为物品个数，c为背包容量>

### \[回溯法基本思想\] ###

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

【优化方法】

剪枝（一）：当前决策放入的物品总重量已经大于背包容量时，没有必要继续决策，此时可以将其左子树剪掉。

剪枝（二）：如果将当前扩展节点后剩下的所有物品都装入还没有目前已求得的最优值大的话，就不在进行决策了，直接返回。

递归回溯时，在当前扩展节点处会通过设置约束函数和限界函数。不满足条件的，剪去相应的子树

【0-1背包算法分析】

对于0-1背包问题，可用一颗完全二叉树表示其解空间，针对上述实例（n=5），解空间树有32个可能的解，解空间树如下图所示。

![5db33f0707d44e9c984d38db12fa6799.png][]

### 法一： ###

> 回溯算法是一种解决问题的通用算法，能够在一个问题的所有解空间中，按深度优先的策略搜索，直到找到所需要的解或者搜索完整个解空间都没有找到解。0-1背包问题是指在限制背包容量的情况下，在一堆物品中选择一部分，使得这些物品的总价值最大。
> 
> C++ 设计回溯算法解决 0-1 背包问题的思路如下：
> 
> 1.  定义一个全局数组 max\_value，用于存储当前找到的最大总价值；
> 2.  定义一个局部数组 current\_weight，用于存储当前已选物品的总重量；
> 3.  定义一个递归函数 backpack，用于搜索某一层的所有可能性；
> 4.  在 backpack 函数中，首先判断是否已经遍历完所有物品，如果是则更新数组 max\_value；
> 5.  如果还没有处理完所有物品，则需要对当前物品进行判断。如果当前物品的重量加上当前已选物品的总重量仍然小于等于背包容量，则将当前物品加入已选物品中，并进入下一层搜索。否则，不加入当前物品，并进入下一层搜索。
> 6.  在递归返回后，需要将当前物品从已选物品中删除，以方便下一次搜索。

一个简单的 C++ 回溯算法解决 0-1 背包问题的示例代码如下：

/*
    * 回溯算法---0-1背包问题
    */
    #include <iostream>
    using namespace std;
    
    const int max_n = 10;
    const int capacity = 50;
    
    int w[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };  // 物品重量数组
    int v[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };  // 物品价值数组
    bool selected[max_n]; // 记录物品是否被选择
    int current_weight = 0;  // 当前已选物品的总重量
    int max_value = 0; // 已找到的最大总价值
    
    // backpack 函数用于搜索某一层的所有可能性
    void backpack(int i) {
        if (i == max_n) {  // 如果已经遍历完所有物品，则更新 max_value
            if (current_weight <= capacity && max_value < v[i]) {
                max_value = v[i];
            }
            return;
        }
    
        if (current_weight + w[i] <= capacity) {  // 如果能将当前物品加入背包
            selected[i] = true;
            current_weight += w[i];
            backpack(i + 1);  // 进入下一层
            current_weight -= w[i];  // 递归返回后，需要将当前物品从已选物品中删除
            selected[i] = false;
        }
    
        backpack(i + 1);  // 进入下一层
    }
    
    int main() {
        backpack(0);  // 从第一个物品开始搜索
        cout << "最大总价值为：" << max_value << endl;
        return 0;
    }

### 法二： ###

#### 代码： ####

头文件：

#pragma once
    #include<iostream>
    #include<cmath>
    #include<vector>
    #include < algorithm>
    using namespace std;

源文件：

/*
    * 回溯算法--01背包
    */
    #include"01背包头文件.h"
    
    const int NUM = 50;
    int c;		//背包容纳的重量
    int n;		//物品数量
    int cw;		//当前重量
    int cv;		//当前价值
    int bestv;	//当前最优价值
    
    //描述每个物品的数据结构
    struct Object {
    	int w;		//物品的重量
    	int v;		//物品的价值
    	double d;	//物品的单位价值重量比（d=v/w）
    }Q[NUM];		//物品的数组
    
    bool cmp(Object a,Object b) {
    	if (a.d>b.d){
    		return true;
    	}
    	else{
    		return false;
    	}
    }
    //限界函数Bound()的实现
    //形参i是回溯的深度
    int Bound(int i) {
    	int cleft = c - cw;  // 背包剩余容纳的重量
    	double b = cv;       // 上界价值
    
    	while (i < n && Q[i].w <= cleft) {  // 尽量装满背包
    		cleft -= Q[i].w;
    		b += Q[i].v;
    		i++;
    	}
    
    	if (i < n) {  // 剩余空间不足以容纳物品 i 时，将物品 i 分配到背包中，直到背包装满
    		b += 1.0 * Q[i].v / Q[i].w * cleft;
    	}
    	return b;
    }
    
    //形参i是回溯的深度，从0开始
    void backtrack(int i){
    	if (i + 1 > n) {
    		bestv = cv;
    		return;
    	}
    	//进入左子树搜索
    	if(cw+Q[i].w<=c) {
    		cw = cw + Q[i].w;
    		cv = cv + Q[i].v;
    		backtrack(i + 1);
    		cw = cw - Q[i].w;
    		cv = cv - Q[i].v;
    	}
    	//进入右子树搜索
    	if(Bound(i+1)>bestv){
    		backtrack(i + 1);
    	}
    }
    
    int main() {
    	cin >> c >> n;							//输入背包容纳的重量和物品数量
    	for (int i = 0; i < n; i++) {
    		cin >> Q[i].w >> Q[i].v;			//输入物品的重量和物品的价值
    		Q[i].d = 1.0 * Q[i].v / Q[i].w;		//物品的单位价值重量比（d=v/w）
    	}				
    
    	//排序
    	sort(Q, Q + n, cmp);
    	backtrack(0);
    	cout << "最大总价值为：" << bestv << endl;   
    	return 0;			
    }

#### 运行结果 ####

![1a37132c2a6a4d8b92fbae119144bc91.png][]

## 代码改进 ##

上面的代码已经实现了 01 背包问题的求解，但是还有一些需要改进的地方，以下是我的建议：

1.  你在回溯函数 backtrack 中使用递归的方式进行搜索。虽然递归可以使得代码更加简洁，但是如果物品数量较大时，可能会导致栈溢出的问题。因此，建议采用迭代的方式进行搜索，使用一个栈来存储搜索状态。
2.  在你的排序函数中，其实不必写成一个 bool 类型的函数，直接写成一个比较函数即可。例如：

bool cmp(Object a, Object b) {
        return a.d > b.d;
    }

3.你在计算排序后的上界时，可能会出现除数为 0 的情况（当背包容量为 0 时）。因此，在计算物品的单位价值时，可以加上一个特判，例如：

if (Q[i].w == 0) {
        Q[i].d = 0;
    } else {
        Q[i].d = 1.0 * Q[i].v / Q[i].w;
    }

4.下面是修改过的代码：

/*
     * 01 背包问题求解，回溯法实现
     * 输入格式：
     * 第一行包含背包容量 c 和物品数量 n，以空格分隔；
     * 接下来 n 行，每行包含一个物品的重量和价值，以空格分隔。
     * 输出格式：
     * 最大总价值
     */
    
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    const int MAXN = 50;
    
    struct Object {
        int w, v;  // 物品重量和价值
        double d;  // 单位价值
    };
    
    bool cmp(Object a, Object b) {
        return a.d > b.d;
    }
    
    int main() {
        int c, n;
        cin >> c >> n;
        vector<Object> items(n);
        for (int i = 0; i < n; i++) {
            cin >> items[i].w >> items[i].v;
            if (items[i].w == 0) {
                items[i].d = 0;
            } else {
                items[i].d = 1.0 * items[i].v / items[i].w;
            }
        }
        sort(items.begin(), items.end(), cmp);  // 按单位价值排序
        int bestv = 0;  // 当前最优解
        vector<int> path(n);  // 存储当前搜索路径
        int i = 0;  // 当前搜索的物品编号
        int cw = 0;  // 当前背包中物品的总重量
        int cv = 0;  // 当前背包中物品的总价值
        while (true) {
            if (i >= n) {  // 遍历完了所有物品，回溯
                if (bestv < cv) {
                    bestv = cv;
                }
                if (path.empty()) {
                    break;  // 遍历完了所有状态，退出
                }
                i = path.back();  // 取出上一个搜索的物品
                path.pop_back();
                cw -= items[i].w;
                cv -= items[i].v;
                i++;  // 进入右子树搜索
            } else if (cw + items[i].w <= c) {  // 左子树搜索
                path.push_back(i);
                cw += items[i].w;
                cv += items[i].v;
                i++;  // 进入左子树搜索
            } else {  // 右子树搜索
                double bound = cv + (c - cw) * items[i].d;  // 计算上界
                if (bound < bestv) {
                    if (path.empty()) {
                        break;  // 遍历完了所有状态，退出
                    }
                    i = path.back();  // 取出上一个搜索的物品
                    path.pop_back();
                    cw -= items[i].w;
                    cv -= items[i].v;
                    i++;  // 进入右子树搜索
                } else {
                    i++;  // 进入左子树搜索
                }
            }
        }
        cout << bestv << endl;
        return 0;
    }

> 这段代码实现了 01 背包问题的回溯算法求解，并且采用了剪枝策略进行优化，基本思路如下：
> 
> 1.  首先，读入背包容量 c 和物品数量 n，以及每个物品的重量和价值。
> 2.  将物品按单位价值从大到小排序，这里采用了 C++ STL 中的 sort 函数。
> 3.  从第一个物品开始进行搜索，使用一个栈来保存搜索路径，路径上的每个节点包含当前已选中的物品编号、当前背包中已装载的物品总重量和总价值。
> 4.  在搜索过程中，对于每个节点，分别考虑进入其左子树和右子树两种情况。左子树表示当前物品被选择放入背包，进入左子树后要将物品的重量和价值加入到当前背包中，并更新搜索路径；右子树表示当前物品不放入背包，进入右子树后只需要更新搜索路径即可。
> 5.  在进入下一个节点之前，使用剪枝策略计算这个节点的上界。这里使用了线性松弛法（Linear Relaxation），即假设当前物品可以部分装入背包中，按单位价值从大到小的顺序装入物品直到背包装满，则此时背包中物品的总价值加上剩余空间能够容纳的物品的单位价值乘以其重量即为当前节点的上界。如果计算出来的上界小于当前已知的最优解，则可以剪枝，放弃进入左子树的搜索，直接进入右子树。因为进入左子树的搜索必然不会得到更优的解。
> 6.  当遍历完所有节点后，输出当前的最优解即可。
> 
> 总体而言，这段代码实现了一个简洁高效的 01 背包问题求解算法。

[5db33f0707d44e9c984d38db12fa6799.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/2a6fa4611fe144bc955cf39184bd84d4.png
[1a37132c2a6a4d8b92fbae119144bc91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/318b045002d044a49ff4147bd3ab3097.png