回溯法解决01背包问题实验报告，01背包回溯法计算时间

#pgc-card .pgc-card-href { text-decoration: none; width: 100%; height: none; PC 风格*/.pgc-card { 框大小： 164 像素；边框： 1 像素94 像素12 像素180 像素；pgc-card:3336 { content: ‘ ‘ 块；左边框120 像素；右： 20 像素；背景大小：覆盖；溢出：相对； 50%) } .pgc-content-title { font-size: #222;line-height: 粗体；文本溢出：省略号； } .pgc-content-desc { font-size: 省略号；padding-top333 60 9px ; 行高em; -webkit-line-clamp: 2;pgc-content-price { font-size: #f85959;pgc-card-buy 宽度{: color: #406599 ; center; pgc-buy -text { 顶部填充： 10 像素} .pgc-icon-buy { 高度： 20 像素；显示： url(https://lf6-cdn-tos.bytescm.com/obj/cdn -static-resource) /pgc /v2/pgc_tpl/static/image/commodity_buy_f2b4d1a.png); } 算法：数据科学基础69.8 购买1.算法概念

回溯法（search/backward method）又称启发式法，是一种根据优化条件向前搜索以实现目标的优化搜索方法。然而，如果你在探索中到达某个点，发现你的第一个选择不是最优的或者没有达到你的目标，你可以退后一步，做出新的选择。这种如果不起作用就返回并重试的技术称为。回溯。有时你会遇到一类问题，你可以分解问题，但没有明确的动态规划或递归解决方案。这种情况下，可以考虑使用回溯技术来解决此类问题。回溯法的优点是程序结构清晰，易于阅读和理解，问题分析大大提高工作效率。但是，对于可以用明显的递归公式迭代解决的问题，最好不要使用回溯方法，因为它很耗时。

2. 算法要素

1. 解决方案空间

使用回溯技术解决实际问题时，首先要确定解的形式并定义问题的解空间。

(1) 该解由n 元组{x1, x2, x3…. xn} 组成。

(2)解值范围

例如0-1背包问题：

0-1背包问题可以抽象为一个容量有限的背包（容量设置为W）。每种产品都有自己的体积w 和价值v。目标是用最大数量的物品装满这个有限容量的背包。有价值的东西。

例如，有3 项，解的形式为{x1, x2, x3}。其解分量xi的取值范围非常简单：xi=0或xi=1。 xi=0 表示第i 件物品不在包里，xi=1 表示第i 件物品在背包里。

xi{0,1}

包含三个物品的0-1 背包问题具有所有可能的解决方案：{0,0,0}、{0,0,1}、{0,1,0}、{0,1, 1}、{1 ,0 ,0}, {1,0,1}, {1,1,0}, {1,1,1}

解空间：是一个由所有可能解组成的空间，我们需要根据问题的约束条件，在解空间内寻找最优解，如下图所示。

解空间越小，搜索效率越高。解空间越大，搜索效率越低。

(3) 搜索解空间

隐式约束是指对是否可以获得问题的可行或最优解决方案的约束。

如果不满足隐式约束，则意味着该问题没有可行的或最优的解决方案，并且不需要沿着该节点的分支进行搜索，这意味着删除该分支也是一样的。因此，隐式约束也称为剪枝函数。本质不是删除分支，而是停止搜索。

例如，在3件背包0-1问题中，如果背包在前两项（x1=1，x2=1）之后变得超重，那么第三件物品就不需要考虑是否修剪完后，如下图所示放入背包中。

隐式约束（剪枝函数）包括约束函数和绑定函数

解空间的大小和剪枝函数的好坏直接影响搜索效率，因此这两项是搜索算法的关键。搜索空间时，有几个术语需要解释。

(1) 扩展节点：正在增长子节点的节点

(2) 活节点：自己已生成的节点，但其所有子节点尚未生成。

(3) 死节点：生成所有子节点的节点

(4)后代：节点E的子树中的所有节点都是E的后代。

(5) 祖先：从节点E到树根的路径上的所有节点都是E的祖先。

2. 解决问题的步骤：

(1)定义解空间

由于解空间的大小对搜索效率有显着影响，因此我们采用回溯方法首先定义一个合适的解空间，并确定解空间，包括解的构造形式和显式约束。

解组织格式：解组织格式标准化为n元组{x1,x2,…….xn}，但具体表达式的含义有所不同。

显式约束：显式约束允许您限制解值的范围。

(2) 确定解决方案空间的组织形式

解决方案空间的组织结构通常由解决方案空间树的图像表示。根据解空间的不同，解空间分为子集树、排列树、m叉树。

(3) 搜索解空间

回溯法遵循深度优先搜索策略，如果发现当前节点不满足解条件或最佳解，则基于约束（约束函数和边界函数）在解空间中寻找问题的可行解。回溯并尝试其他路径。

如果你的问题只需要可行解，则只需要设置一个约束函数。如果想要得到最优解，就需要设置约束和极限函数。

解的组织格式是一般的n元组格式，解的组织结构是解空间的图像表示。解空间和隐式约束是控制搜索效率的关键。显式约束控制解空间

3. 算法设计流程

01 我们以背包问题为例。假设有n件物品，每件物品i都有一个价值vi、重量wi和购物车容量W。每个项目只有一个项目。加载还是不加载，如果不能拆分，如何加载总价值最高的物品？

2、设计流程

(1)定义问题解决空间

每个项目只有两种状态：已加载或已卸载。使用变量xi来表示第i个商品是否被加载到购物车中的行为。 “0”表示未装入背包，“1”表示装入背包。装入背包中，xi的值为0或1，i=1,2,3,4,5…。第i 件商品已加载到购物车中。 xi=1 不是。已装入购物车。该问题的解决方案格式是一个n 元组，其中每个分量的值为0 或1。

从现在开始，问题求解空间变为{x1,x2,x3,xi,xn}。这里，显式约束是xi=0 或1，i=1,2,3.n。

(2)确定解空间的组织结构

问题的解空间描述了2的n次方可能解的数量，即由n个元素组成的集合的所有子集的数量。例如，对于包含三种产品的购物车问题，解空间为{0,0,0}, {0,0,1}, {0,1,0}, {0,1,1}, { 1 ,0, 0}, {1,0,1}, {1,1,0}, {1,1,1}。这个问题有2^3个解

(3) 搜索解空间

[1] 限制

解空间包含2 的n 次方可能的解。因此，如果某些物品无法装载，则必须设置约束来确定装载物品的总重量是否超过总容量。否则，这是一个可行的解决方案。搜索过程将不再搜索导致不可行解的节点及其子节点。限制条件是：

w1x1 + w2x2 + w3x3+….=W

[2] 边界条件

可能有多种可行的解决方案。该问题的目标是找到可行的解决方案或最佳解决方案，使购物车中加载的商品的总价值最大化。因此，必须设置边界条件来加快最优解的速度。

解空间的组织结构决定了对于任意中间节点z（中间状态），从根节点到z节点的分支所代表的状态，以及从z到其后代节点的分支所代表的状态。是不确定的。换句话说，如果解空间树中z的层数为t，则表示第1项到第t-1项的状态已经确定。为了方便地确定第t 个项目的状态，我们只需要沿着z 的分支展开即可。接下来，确定前t 个项目的状态。然而，从t+1到n的项目状态仍然不确定。这样，确定前t件商品的状态后，当前购物车中的商品的总价就用cp表示。已加载项目的高值不一定是最佳的，因为仍有未决定的项目。

由于我们还不知道第t+1到n项的实际情况，所以我们只能使用估计。假设从第t+1 件商品到第n 件商品的所有商品都已添加到购物车中。因此，第t+1 个产品到第n 个产品的总价值为cp + rp。可能的解值的上限如下图所示。

如果该值的上界小于等于当前搜索到的最优值（最优值用bestp表示，初始值为0），则表示无法从中间节点z继续搜索到后裔。如果探索节点以获得比当前更好的可行解，则无需继续探索。否则，继续搜索z 的后代节点。

cp + rp 最高p

3. 搜索流程

从根节点开始，搜索是深度优先的。根节点是第一个活动节点，也是当前的扩展节点。一致认为子集树的左分支的值为“1”，因此沿着扩展节点的左分支延伸表示项目的负载。这时需要判断是否可以加载该item，即是否满足约束条件，如果满足约束条件，则生成左子节点，并成为当前节点。如果没有建立扩展节点，则继续扩展至深度节点。然后左子节点成为活动节点，切断扩展节点的左分支并沿着其右分支延伸。右侧的分支代表该产品尚未加载到购物车中，这绝对可以得出可行的解决方案。但是沿着右边的分支延伸能否得到最优解呢？这需要由边界条件来确定。如果满足边界条件，则意味着可以得出最优解。即生成右子节点，右子节点成为活节点和当前扩展节点，并继续向深度扩展。 Node；如果不满足边界条件，则扩展节点被切断并追溯到其最近的祖先活节点。搜索过程终止，直到所有活节点都变成死节点。

4. 算法示例

(1)、案例1

假设您有4 件商品。每个项目的权重w 为(2, 5, 4, 2)，值v 为(6, 3, 5, 4)。袋子中可放入的总容量W如下。 10. 问题我应该在包里装哪些物品才能发挥最大价值？

1. 算法设计流程

(1)、初始化

sumw和sumv分别用于统计所有物品的总重量和总价值。总计=2+5+4+2=13，

由于sumv=6 + 3 + 5 +4=18，我们无法完全加载sumv W，因此我们必须搜索并求解它。初始化当前购物车中的商品重量cw=0；当前购物车中的商品价值bestp=0；

(2)、开始搜索第1层(t=1)。

要扩展1号节点，首先求cw + w[1]=2 W，满足约束条件，扩展左分支。

如果x[1]=1，cw=cw + w[1]=2，cp=cp + v[1]=6，则生成如图所示的2号节点。

(3) 展开2号节点(t=2)

首先确定cw + w[2]=7 W，满足约束，并以x[2]=1扩展分支。

cw=cw+w[2]=7，cp=cp+v[2]=9，生成如图所示的3号节点。

(4) 展开3号节点(t=3)

首先确定cw + w[3]=11 W，超出了购物车的容量，无法添加第三件商品。接下来，判断bound(t + 1)是否大于bestp。 bound(4) 中唯一剩余的项目是第四个项目(rp=4)。

由于cp + rp=13，bestp=0，满足边界条件，右子树被扩展。生成x[3]=0的节点4，如图所示。

(5) 展开节点4(t=4)

首先确定cw + w[4]=9 W，满足约束条件，展开左分支。设x[4]=1。

CW=CW + W[4]=9，CP=CP + V[4]=13，生成节点号5

(6) 展开5号节点(t=5)

t n ，求当前最优解。使用bestx[]保存当前最优解。 {1,1,0,1}，保存当前最优解。 bestp=cp=13，节点5成为死节点。

(7) 返回节点No.4(t=4)，并返回节点No.2。

回溯到节点号4。回溯时，cw=cw w[4]=7，cp=cp v[4]=9。我们如何添加它以及如何减去它？节点4的右子树还没有生成。检查bound(t+1)是否大于bestp。 rp=0，cp + 无剩余物品。

rp = 9，bestp = 13，因此不满足界限条件，不能在扩展4号右子树节点。4号节点成为死节点
向上回溯，回溯到3号节点，3号节点的左右孩子均已考察过，是死节点
向上回溯到2号节点，回溯时cw = cw – w[2] = 2，cp = cp – v[2] =6。怎么加上去怎么减去
如下图所示：

（8）扩展节点2（t = 2）
2号节点右子树还未生成，考察bound（t + 1）是否大于bestp，bound(3)中剩余物品为第3、第4个，rp = 9 ， cp + rp =15 ，bestp = 13，因此满足界限条件，扩展右子树。令x2 = 0生成6号节点

（9）扩展6号节点（t = 3）
首先判断cw + w[3] = 6 <W，满足约束条件，扩展左分支，令x[3] =1，
Cw= cw + w[3] = 6，cp = cp + v[3] =11，生成7号节点，如图所示：

（10）扩展7号节点（t = 4）
首先判断 cw + w[4] = 8 < W，满足约束条件，扩展左分支，令x[4] =1，
cw = cw + w[4] = 8，cp = cp + v[4] = 15，生成8号节点，如图：

（11）扩展8号节点（t =5）
t > n（n=4），找到当前个最优解，用bestx[]保存当前最优解{1，0，1，1}，保存当前最优解值bestp = cp = 15 ， 8号节点成为死节点
向上回溯到7号节点，回溯时cw = cw – w[4] = 6、cp = cp –v[4] =11，怎么加的怎么减去
（12）扩展7号节点（t =4）
7号节点的右孩子树还没有生成，考察bound(t + 1)是否大于bestp，bound(5)中没有剩余产品, rp =0、 cp + rp =11，bestp = 15，因此不满足界限条件，不再扩展7号节点的右子树。7号节点成为死节点
向上回溯，回溯到6号节点，回溯时cw = cw – w[3] = 2、cp=cp-v[3]=6怎么加的怎么减
（13）扩展6号节点（t =3）
6号节点的右子树还未生成，考察bound(t+1)是否大于bestp，bound(4)中剩余物品是第4个，rp = 4、cp + rp = 10，bestp=15因此不满足界限条件，不再扩展6号节点的右子树
向上回溯，回溯到2号节点，2号节点的左右孩子均已考察过，是死节点
向上回溯1号节点，回溯时cw=cw-w[1]=0、cp=cp-v[1]=0，怎么加的，怎么减
（14）扩展1号节点（t = 1）
1号节点的右子树还未生成，考察bound(t+1)是否大于bestp，bound(2)中剩余物品为第2、3、4个，rp =12、cp+rp=12、bestp=15，因此不满足限界条件，不再扩展1号节点的右子树，1号节点为死节点，所有节点都是死节点，算法结束。如图所示：

2、代码实现
（1）伪代码
【1】计算上界的函数：
计算上界是指计算已装入物品价值cp与剩余物品的总价值rp之和。我们已经知道已装入物品价值cp，剩余物品我们不确定要装入哪些，我们按照假设都装入的情况估算，即按最大值计算（剩余物品总价值），因此得到的值是可装入物品价值的上界
//计算上界：已装入物品价值+剩余物品总价值
double bound(int i )
{
int rp = 0;//剩余物品为第i- n种物品
while( i <= n )//依次计算剩余物品的价值
{
rp + = v[i];
i++ ;
}
return cp + rp ;//返回上界
}
【2】按约束条件和限界条件搜索求解函数
t表示当前扩展节点在第t层，cw表示当前已放入物品的重量，cp表示当前已放入物品的价值
如果t > n表示已经到达叶子节点，记录最优值最优解，返回。否则，判断满足约束条件，满足则搜索左子树，因为左子树表示放入该物品，所以令x[t]=1，表示放入第t个该物品。cw + = w[t]，表示当前已放入该物品的重量增加w[t]。cp + = v[t]，表示当前已放入物品的价值增加v[t]。backTrack(t+1)表示递推，深度优先搜索第t+1层。回归时即向上回溯时，要把增加的值减去，cw- =w[t]，cp-=v[t]
判断是否满足限界条件，满足则搜索右子树。因为右子树表示不放入该物品，所以令x[t]=0。当前已放入物品的重量、价值均不改变。backTrack(t+1)表示递推，深度优先搜索第t+1层
//表示当前扩展节点在第t层
void backTrack(int t)
{
if(t > n)//已经到达叶子节点
{
for(j = 1 ; j < = n ; j++)
{
bestx[j]=x[j];
}
//保存当前最优解
bestp = cp;
return ;
}
//如果满足约束条件则搜索左子树
if(cw + w[t] <= W)
{
x[t] = 1;
cw + = w[t];
cp + = v[t];
backTrack(t+1);
cw – = w[t];
cp – = v[t];
}
//如果满足限界条件则搜索右子树
if(bound(t + 1) > bestp)
{
x[t] = 0;
backTrack(t+1);
}
}
完整程序代码如下：
#include <iostream>
#include <string>
#include <algorithm>
#define M 105
using namespace std;
//n表示n个物品，W表示购物车的容量
int i , j , n , W;
//w[i]表示第i个物品的重量，v[i]表示第i个物品的价值
double w[M] , v[M];
//表示第i个物品是否放入购物车
bool x[M];
//当前重量
double cw;
//当前价值
double cp;
//当前最优价值
double bestp;
//当前最优解
bool bestx[M];
//计算上界，即剩余物品总价值
double bound (int i )
{
//剩余物品为i–n种物品
int rp = 0;
//以物品为单位重量价值重量价值递减的顺序装入物品
while(i <= n )
{
rp + = v[i];
i ++;
}
return cp + rp;
}
//用于搜索空间数，t表示当前扩展节点在第t层
void backTrack( int t )
{
if( t > n )//已经到达叶子节点
{
for(j = 1;j < = n; j++)
{
//保存当前最优解
bestx[j] = x[j];
}
bestp = cp;//保存当前最优值
return;
}
//如果满足限制条件则搜索左子树
if(cw + w[t] <= W)
{
x[t] = 1;
cw + = w[t];
cp + = v[t];
backTrack(t + 1);
cw – = w[t];
cp – = v[t];
}
//如果满足限制条件则搜索右子树
if( bound(t + 1) > bestp)
{
x[t] = 0;
backTrack( t + 1);
}
}
void demo(double W , int n)
{
//初始化当前放入购物车的物品重量为0
cw = 0;
//初始化当前放入购物车的物品价值为0
cp = 0;
//初始化当前最优解
bestp = 0;
//用来统计所有物品的总重量
double sumw = 0.0;
//用来统计所有物品的总价值
double sumv = 0.0;
for(i = 1; i <= n;i++)
{
sumv + = v[i];
sumw + = w[i];
}
if(sumw <= W)
{
bestp = sumv;
count << “放入购物车的物品最大价值为：” <<bestp<<endl;
cout <<“所有的物品均放入购物车”;
return;
}
backTrack(1);
cout <<“放入购物车的物品最大价值为：”<<bestp<<endl;
cout <<“放入购物车的物品序号为：”;
for(i = 1;i < = n; i ++)
{
if(bestx[i] ==1)
cout <<i<<” “;
}
cout<<endl;
}
int main()
{
cout<<“请输入物品的个数n：”;
cin>>n;
cout<<“请输入购物车的容量W：”;
cin>>W;
cout<<“请依次输入每个物品的重量w和价值v,用空格分开” ;
for(i = 1;i <= n;i++)
{
cin>>w[i]>>v[i];
}
demo(W,n);
return 0;
}
五、算法时间复杂度和空间复杂度分析
（1）时间复杂度
回溯法的运行时间取决于它在搜索过程中生成的节点数。而限界函数可以大大减少所生成的节点个数，避免无效搜索，加快搜索速度
左节点需要判断约束函数，右节点需要判断限界函数，那么最坏有多少个左节点和右节点呢？我们看规模为n的子集树，最坏情况下的状态如图：

【1】总的结点个数：

【2】左右孩子结点个数
总的结点个数减去根节点再除2就得到左右孩子结点的个数，左右孩子结点的个数为：

约束函数的时间复杂度为O(1)，限界函数时间复杂度为O(n)。最坏情况下有

个左孩子结点调用约束函数
有

个右孩子结点调用限界函数，故回溯法的时间复杂度为

（2）空间复杂度
回溯法会产生解空间，在搜索的任何时刻，仅保留从开始结点到当前扩展结点的路径，从开始结点起最长的路径为n。程序中我们使用bestp[]数组记录最长路径作为最优解，所以该算法的空间复杂度为O(n)
六、算法优化
在上面程序中上界函数是当前价值cp与剩余物品总价值rp之和，这个估值过高了，因为剩余物品的重量很可能是超过购物车容量的。因此我们可以缩小上界，从而加快剪枝速度，提高搜索效率
上界函数bound()：当前价值cp+剩余容量可容纳的剩余物品的最大值brp
为了更好地计算和运用上界函数剪枝，先将物品按照其单位重量价值（价值/重量）从大到小排序，然后按照排序后的顺序考察各个物品
#include <iostream>
#include <string>
#include <algorithm>
#define M 105
using namespace std;
//n表示物品个数，W表示购物车容量
int i , j , n , W;
//w[i]表示第i个物品重量，v[i]表示第i个物品价值
double w[M] , v[M];
//x[i]=1表示第i个物品放入购物车
bool x[M];
double cw;//当前重量
double cp;//当前价值
double bestp;//当前最优值
double bestx[M];//当前最优解
/**
*计算上界：
*将剩余物品装满剩余的背包容量时所能获得的最大价值
*/
double bound(int i)
{
//剩余物品为第i–n种物品
double cleft = W – cw;//剩余容量
double brp =0.0;
while(i <= n && w[i] < cleft)
{
cleft -=w[i];
brp +=v[i];
i++;
}
//采用切割的方式装满背包，这里是求上界，求解时不允许切割
if(i <=n)
{
brp+=v[i]/w[i]*cleft;
}
return cp + brp;
}
//用于搜索空间数，t表示当前扩展结点在第t层
void backTrack(int n)
{
if(t > n)//已经到达叶子节点
{
for(j = 1;j <=n;j++)
{
bestx[j]=x[j];
}
bestp=cp;//保存当前解
return;
}
//如果满足限制条件则搜索左子树
if(cw + w[t]<=W)
{
x[t]=1;
cw+=w[t];
cp+=v[t];
backTrack(t+1);
cw-=w[t];
cp-=v[t];
}
//如果满足限制条件则搜索右子树
if(bound(t+1) > bestp)
{
x[t] = 0;
backTrack(t+1);
}
}
//定义物品结构，包括序号和单位重量价值
struct Object
{
int id; //物品序号
double d;//单位重量价值
};
//按物品单位重量价值由大到小排序
bool cmp(Object a1,Object a2)
{
return a1.d>a2.d;
}
void demo(int W,int n)
{
//初始化
//初始化放入物品重量为0
cw=0;
//初始化放入物品价值为0
cp=0;
//初始化当前最优值为0
bestp=0;
//用来统计所有物品总重量
double sumw = 0;
//用来统计所有物品总价值
double sumv=0;
//物品结构体类型，用于按单位重量价值（价值/重量比）排序
Object Q[n];
//辅助数组，用于把排序后的重量和价值传递给原来的重量价值数组
double a[n+1] , b[n+1];
for(i = 1;i <=n ;i++)
{
Q[i-1].id = i;
Q[i-1].d = 1.0*v[i]/w[i];
sumv+=v[i];
sumw+=w[i];
}
if(sumw <= W )
{
bestp = sumv;
cout<<“放入物品最大价值为：”<<bestp<<endl;
cout<<“所有物品均放入”;
return;
}
//按单位重量价值（价值/重量比）从大到小排序
sort(Q ,Q + n,cmp);
for(i=1;i<=n;i++)
{
//把排序后的数据传递给辅助数组
a[i]=w[Q[i-1].id];
b[i]=v[Q[i-1].id];
}
for(i=1;i<=n;i++)
{
//把排序后的数据传递给w[i]
w[i] = a[i];
v[i] = b[i];
}
backTrack(1);
cout<<“放入的物品最大价值为：”<<bestp<<endl;
cout<<“放入购物车的物品序号为”;
for(i =1;i <= n;i++)
{
if(bestx[i]==1)
cout<<Q[i-1].id<<“”;
}
cout<<endl;
}
int main()
{
cout<<“请输入物品的个数n：”;
cin >>n;
cout<<“请输入购物车的容量W：”;
cin >>W;
cout<<“请依次输入每个物品的重量w和价值v，用空格分开”;
for(i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
demo(W,n);
return 0;
}
（1）时间复杂度：约束函数时间复杂度为O(1)，限界函数时间复杂度为O(n)。最坏情况下有O(2的n次方)个左孩子调用约束函数，有O(2的n次方)个右孩子调用界限函数，回溯算法backTrack需要计算时间为O(n*2的n次方)。排序函数时间复杂度为O(n Log n)，这是考虑最坏情况。实际上，经过上界函数优化后，剪枝速度很快，根本不需要生成所有节点
（2）空间复杂度：除了记录最优解数组外，还是用一个结构体数组用于排序，两个辅助数组传递排序后的结果，这些数组的规模都是n，因此空间复杂度仍为O(n)