2023年8月1日发(作者：)

一、实验目的

（1） 理解回溯法的思想。

（2） 掌握一些经典的问题解决方法。

二、实验内容与实验步骤

0-1背包问题

 问题描述

给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

 编程任务

利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量ｘi

(ｘi = 0 或１，ｘi = 0表示物体ｉ不放入背包，ｘi ＝1表示把物体ｉ放入背包），

使得尽量多的价值装入背包。

 数据输入

由文件提供输入数据n，c，及每个物品的重量w[ ]和价值v[ ]。

 结果输出

程序运行结束时，将最优解输出到文件中。

输入文件示例

4

5

输出文件示例

1 1 0 1

2 1 3 2

12 10 20 15

三、实验环境

操作系统

调试软件

上机地点

Windows 7

VC++6.0

综合楼211 四、问题分析

（1） 分析要解决的问题，给出你的思路，可以借助图表等辅助表达。

01背包问题用回溯法实现就是要枚举其所有的解空间，时间复杂度为O(2n)左右。

搜索的具体方法如下：

对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树：

基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。

利用回溯算法写还可以加入一些优化，进行剪枝，因为很多情况是没有意义的，例如当重量大于背包容量的时候，没有必要对剩下的物品再来决策了。或者将剩下的所有物品都选取其总价值也没有目前已经求得的方案的价值还大的话，也是可以剪枝的。

（2） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。

时间复杂度估计：O(2n)

因为物品只有选与不选2个决策，而总共有n个物品，所以时间复杂度为O(2n)。

空间复杂度估计：O(n) 因为递归栈最多达到n层，而且存储所有物品的信息也只需要常数个一维数组，所以最终的空间复杂度为O(n)。

五、问题解决

（1） 根据对问题的分析，写出解决办法。

根据上面的分析，搜索的具体方法如下：

对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树，由父亲节点往下搜索的时候，往左表示选择该物品，并且将该物品的重量和价值追加到总重量和总价值中，最后，当到达第n+1层的时候，表示所有的物品都已经决策完了，可以比较和更新最优值。

当所有的分支和节点都遍历完时，此时的最优值就是原问题的最优值。

优化方法：

剪枝一：可以进行剪枝，因为很多情况是没有意义的，当重量大于背包容量的时候，没有必要对剩下的物品再来决策了。

剪枝二：将剩下的所有物品都选取其总价值也没有目前已经求得的方案的价值还大的话，也可以返回。

（1） 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。

void Knapsack(Typep p[ ], Typew w[ ], Typew c, int n)

{ //为Knap::Backtrack 初始化

Typew W = 0;

Typep P = 0;

FILE *fp;

Object * Q = new Object[n];

for ( int i = 1; i <= n; i++ ) {

Q[ i-1]. ID = i;

Q[ i-1]. d =1.0*p[i]/w[i];

P += p[i];

W += w[i];

}

Sort( Q, n);//对背包里的物品按性价比排序

Knap < Typew, Typep > K;

K.p = new Typep[ n+1 ];

K.w = new Typew[ n+1 ];

K.x = new int[ n+1 ];

for (i = 1; i <= n; i++){

K.p[i] = p[ Q[i-1].ID];

K.w[i] = w[ Q[i-1].ID];

}

= 0;

K. cw = 0;

K.c = c;

K.n = n;

= 0;

// 回溯搜索

ack(1);

delete [ ] Q;

delete [ ] K.w;

delete [ ] K.p;

if ((fp=fopen("","w"))==NULL)

{

fprintf(stderr, "Cannot open input file.n");

exit(0);

}

fprintf(fp,"%d,%d,%d,%d",K.x[4],K.x[1],K.x[2],K.x[3]);

fclose(fp);

cout<<"当前最优装配:";

cout<

for (i=1;i

{

cout<<" "<< K.x[i] ;

}

cout<

}

template

void Knap:: Backtrack( int i)

{

if ( i > n ) {

bestp = cp;

return; }

if( cw + w[i] <= c){

x[i] = 1;

cw += w[i];

cp += p[i];

Backtrack(i+1);

cw -= w[i];

cp -= p[i];

}

if( Bound(i+1)> bestp)

x[i] = 0;

Backtrack(i+1);

}

template

Typep Knap:: Bound( int i)

{ //计算上界

Typew cleft = c-cw; //剩余容量

Typep b = cp;

//以物品单位重量价值递减序装入物品

while ( i<= n && w[i]<= cleft) {

cleft -= w[i];

b += p[i];

i++;

}

//装满背包

if( i<=n ) b+= p[i]/w[i]*cleft;

return b;

}

算法复杂度：由于计算上界函数Bound需要O(n)时间，在最坏情况下有O(2n)个右儿子结点需要计算上界函数，故解0-1背包问题的回溯算法Backtrack所需的计算时间为O(n2n)。

算法创新：增加了对于上限的处理函数，计算右子树中解的上界时，将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，由此得到的价值是右子树的上界，如果这个上界不能达到当前得到的最优值，则不搜索该子树。

（2） 你在调试过程中发现了怎样的问题？又做了怎样的改进？

答：在调试过程中，对于背包中物品顺序的保存始终存在问题，应该是1011，可是总是无法得出正确的结果，所以，我对数组x[i]进行了单步调试，继而发现了在前面回溯法的设计过程中存在缺陷，将x[4]误当成了x[0]，后来经过改正输出正确。 六、实验结果总结

本实验也是自己独立完成，从设计回溯法开始，到实现01背包问题的求解，从中我学到了很多，从错误的改正过程中逐渐完成了对于问题的求解。

1.程序运行截图：

2.回答以下问题：

（1） 算法实现的复杂度在问题规模很大时可以接受吗？

答：不可以接受。因为该算法是指数级别的时间复杂度为O(n*2)，当n较大时，也能在一定时间内无法得出结果。空间复杂度为O(n)，还可以接受。

但是综合上面分析，时间复杂度成为极大地瓶颈。所以规模很大时不可以接受。

（2） 如果不用回溯方法还能想到其他的解决方式吗？和回溯法相比会有更好的效率吗？

还可以用基于动态规划思想的算法。在考虑第i个物品的决策时，前面的物品的选择方案就成为了子问题，可以建立如下状态转移方程：

nf[i1][j]

f[i][j]maxf[i1][jw[i]]v[i]其中f[i][j]表示前i个物品装入容量不超过j的背包的最优值。

时间复杂度为O(n*C)，其中C为背包容量。时间复杂度比回溯法要好很多。

（3） 所选用的数据结构合适吗？

答：合适，只用到一维数组。使用的数据结构简单，易理解。能够对数组中的每个元素随机访问。

（4） 该算法都存在哪几类可能出现的情况，你的测试完全覆盖了你所想到的这些情况吗，测试结果如何？

答：测试全面。

输入规模为0时，程序自动结束。

输入总重量小于背包容量时，结果为所有物品的价值总和。

输入的总重量大于背包容量时，结果为能装入所有方案中最大的值。

（5） 叙述通过实验你对回溯法方法的理解及其优缺点

优点： 回溯法在普通的深度优先搜索的基础上增加了限界函数，对不必要的解空间树进行剪枝，使得可行解的数量大大减少，增加了搜索速度。

回溯法的设计也非常简单，即简单的枚举搜索策略，只需要分析细节过程就能增加剪枝的操作。

另外，空间复杂度通常非常小，只有搜索深度左右的空间。

缺点： 回溯法虽然设计简单，但是时间复杂度非常高，通常是指数级别的。而且回溯法的难点在于限界函数的设计。

而且回溯法通常需要遍历完所有的解空间才能得出最优值，而不是像宽度优先搜索一样第一次求出的值便是最优值。

七、附录

参考资料：

《算法导论》

2023年8月1日发(作者：)

一、实验目的

（1） 理解回溯法的思想。

（2） 掌握一些经典的问题解决方法。

二、实验内容与实验步骤

0-1背包问题

 问题描述

给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

 编程任务

利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量ｘi

(ｘi = 0 或１，ｘi = 0表示物体ｉ不放入背包，ｘi ＝1表示把物体ｉ放入背包），

使得尽量多的价值装入背包。

 数据输入

由文件提供输入数据n，c，及每个物品的重量w[ ]和价值v[ ]。

 结果输出

程序运行结束时，将最优解输出到文件中。

输入文件示例

4

5

输出文件示例

1 1 0 1

2 1 3 2

12 10 20 15

三、实验环境

操作系统

调试软件

上机地点

Windows 7

VC++6.0

综合楼211 四、问题分析

（1） 分析要解决的问题，给出你的思路，可以借助图表等辅助表达。

01背包问题用回溯法实现就是要枚举其所有的解空间，时间复杂度为O(2n)左右。

搜索的具体方法如下：

对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树：

基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。

利用回溯算法写还可以加入一些优化，进行剪枝，因为很多情况是没有意义的，例如当重量大于背包容量的时候，没有必要对剩下的物品再来决策了。或者将剩下的所有物品都选取其总价值也没有目前已经求得的方案的价值还大的话，也是可以剪枝的。

（2） 分析利用你的想法解决该问题可能会有怎样的时空复杂度。

时间复杂度估计：O(2n)

因为物品只有选与不选2个决策，而总共有n个物品，所以时间复杂度为O(2n)。

空间复杂度估计：O(n) 因为递归栈最多达到n层，而且存储所有物品的信息也只需要常数个一维数组，所以最终的空间复杂度为O(n)。

五、问题解决

（1） 根据对问题的分析，写出解决办法。

根据上面的分析，搜索的具体方法如下：

对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树，由父亲节点往下搜索的时候，往左表示选择该物品，并且将该物品的重量和价值追加到总重量和总价值中，最后，当到达第n+1层的时候，表示所有的物品都已经决策完了，可以比较和更新最优值。

当所有的分支和节点都遍历完时，此时的最优值就是原问题的最优值。

优化方法：

剪枝一：可以进行剪枝，因为很多情况是没有意义的，当重量大于背包容量的时候，没有必要对剩下的物品再来决策了。

剪枝二：将剩下的所有物品都选取其总价值也没有目前已经求得的方案的价值还大的话，也可以返回。

（1） 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。

void Knapsack(Typep p[ ], Typew w[ ], Typew c, int n)

{ //为Knap::Backtrack 初始化

Typew W = 0;

Typep P = 0;

FILE *fp;

Object * Q = new Object[n];

for ( int i = 1; i <= n; i++ ) {

Q[ i-1]. ID = i;

Q[ i-1]. d =1.0*p[i]/w[i];

P += p[i];

W += w[i];

}

Sort( Q, n);//对背包里的物品按性价比排序

Knap < Typew, Typep > K;

K.p = new Typep[ n+1 ];

K.w = new Typew[ n+1 ];

K.x = new int[ n+1 ];

for (i = 1; i <= n; i++){

K.p[i] = p[ Q[i-1].ID];

K.w[i] = w[ Q[i-1].ID];

}

= 0;

K. cw = 0;

K.c = c;

K.n = n;

= 0;

// 回溯搜索

ack(1);

delete [ ] Q;

delete [ ] K.w;

delete [ ] K.p;

if ((fp=fopen("","w"))==NULL)

{

fprintf(stderr, "Cannot open input file.n");

exit(0);

}

fprintf(fp,"%d,%d,%d,%d",K.x[4],K.x[1],K.x[2],K.x[3]);

fclose(fp);

cout<<"当前最优装配:";

cout<

for (i=1;i

{

cout<<" "<< K.x[i] ;

}

cout<

}

template

void Knap:: Backtrack( int i)

{

if ( i > n ) {

bestp = cp;

return; }

if( cw + w[i] <= c){

x[i] = 1;

cw += w[i];

cp += p[i];

Backtrack(i+1);

cw -= w[i];

cp -= p[i];

}

if( Bound(i+1)> bestp)

x[i] = 0;

Backtrack(i+1);

}

template

Typep Knap:: Bound( int i)

{ //计算上界

Typew cleft = c-cw; //剩余容量

Typep b = cp;

//以物品单位重量价值递减序装入物品

while ( i<= n && w[i]<= cleft) {

cleft -= w[i];

b += p[i];

i++;

}

//装满背包

if( i<=n ) b+= p[i]/w[i]*cleft;

return b;

}

算法复杂度：由于计算上界函数Bound需要O(n)时间，在最坏情况下有O(2n)个右儿子结点需要计算上界函数，故解0-1背包问题的回溯算法Backtrack所需的计算时间为O(n2n)。

算法创新：增加了对于上限的处理函数，计算右子树中解的上界时，将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，由此得到的价值是右子树的上界，如果这个上界不能达到当前得到的最优值，则不搜索该子树。

（2） 你在调试过程中发现了怎样的问题？又做了怎样的改进？

答：在调试过程中，对于背包中物品顺序的保存始终存在问题，应该是1011，可是总是无法得出正确的结果，所以，我对数组x[i]进行了单步调试，继而发现了在前面回溯法的设计过程中存在缺陷，将x[4]误当成了x[0]，后来经过改正输出正确。 六、实验结果总结

本实验也是自己独立完成，从设计回溯法开始，到实现01背包问题的求解，从中我学到了很多，从错误的改正过程中逐渐完成了对于问题的求解。

1.程序运行截图：

2.回答以下问题：

（1） 算法实现的复杂度在问题规模很大时可以接受吗？

答：不可以接受。因为该算法是指数级别的时间复杂度为O(n*2)，当n较大时，也能在一定时间内无法得出结果。空间复杂度为O(n)，还可以接受。

但是综合上面分析，时间复杂度成为极大地瓶颈。所以规模很大时不可以接受。

（2） 如果不用回溯方法还能想到其他的解决方式吗？和回溯法相比会有更好的效率吗？

还可以用基于动态规划思想的算法。在考虑第i个物品的决策时，前面的物品的选择方案就成为了子问题，可以建立如下状态转移方程：

nf[i1][j]

f[i][j]maxf[i1][jw[i]]v[i]其中f[i][j]表示前i个物品装入容量不超过j的背包的最优值。

时间复杂度为O(n*C)，其中C为背包容量。时间复杂度比回溯法要好很多。

（3） 所选用的数据结构合适吗？

答：合适，只用到一维数组。使用的数据结构简单，易理解。能够对数组中的每个元素随机访问。

（4） 该算法都存在哪几类可能出现的情况，你的测试完全覆盖了你所想到的这些情况吗，测试结果如何？

答：测试全面。

输入规模为0时，程序自动结束。

输入总重量小于背包容量时，结果为所有物品的价值总和。

输入的总重量大于背包容量时，结果为能装入所有方案中最大的值。

（5） 叙述通过实验你对回溯法方法的理解及其优缺点

优点： 回溯法在普通的深度优先搜索的基础上增加了限界函数，对不必要的解空间树进行剪枝，使得可行解的数量大大减少，增加了搜索速度。

回溯法的设计也非常简单，即简单的枚举搜索策略，只需要分析细节过程就能增加剪枝的操作。

另外，空间复杂度通常非常小，只有搜索深度左右的空间。

缺点： 回溯法虽然设计简单，但是时间复杂度非常高，通常是指数级别的。而且回溯法的难点在于限界函数的设计。

而且回溯法通常需要遍历完所有的解空间才能得出最优值，而不是像宽度优先搜索一样第一次求出的值便是最优值。

七、附录

参考资料：

《算法导论》