回溯法实验01背包问题教学文案.docx
《回溯法实验01背包问题教学文案.docx》由会员分享，可在线阅读，更多相关《回溯法实验01背包问题教学文案.docx（12页珍藏版）》请在冰点文库上搜索。
回溯法实验01背包问题教学文案
回溯法实验（0-1背包问题）
算法分析与设计实验报告
第五次附加实验
姓名
学号
班级
时间
12.26上午
地点
工训楼309
实验名称
回溯法实验（0-1背包问题）
实验目的
1.掌握回溯法求解问题的思想
2.学会利用其原理求解0-1背包问题
实验原理
基本思想：
0-1背包问题是子集选取问题。
0-1背包问题的解空间可以用子集树表示。
在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。
当右子树中有可能含有最优解时，才进入右子树搜索。
否则，将右子树剪去。
基本解题步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
实验步骤
（1）首先搜索解空间树，判断是否到达了叶结点；
（2）如果左子结点是一个可行节点，就进入左子树；
（3）当右子树有可能包含最优解的时候才进入右子树，计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包；
（4）利用深度优先搜索整个解空间树，直到将所有的最优解找出位置。
关键代码
template
voidKnap:
:
Backtrack（inti）
{
if（i>n）//到达叶子节点
{
bestp=cp;//更新最优值
return;
}
if（cw+w[i]<=c）//进入左子树
{
cw+=w[i];
cp+=p[i];
Backtrack（i+1）;//回溯
//回溯结束回到当前根结点
cw-=w[i];
cp-=p[i];
}
//进入右子树，条件是上界值比当前最优值大，否则就将右子树剪掉
if（Bound（i+1）>bestp）
{
Backtrack（i+1）;
}
}
测试结果
当输入的数据有解时：
当输入的数据无解时：
当输入的数据稍微大点时：
实验分析
在实验中并没有生成多组数据，进行比较，也没有利用随机生成函数，因为在这种有实际有关联的问题中，利用随机生成函数生成的数据是十分的不合适的，在此我们只需要验证该程序是否正确即可。
0-1背包问题和之前的最优装载其实质上一样的，都是利用解空间树，通过深度优先搜索子集树，通过利用上界函数和一些剪枝策略，从而得到最优解。
由于数据较小，所以时间上并不能反映出什么东西。
实验心得
在这一章的回溯算法中，我们用的比较多的就是；利用子集树来进行问题的探索，就例如上图是典型的一种子集树，在最优装载、0-1背包都是利用了这种满二叉树的子集树进行求解，然后通过深度优先的策略，利用约束函数和上界函数，将一些不符合条件或者不包含最优解的分支减掉，从而提高程序的效率。
对于0-1背包问题我们基本上在每一个算法中都有这么一个实例，足以说明这个问题是多么经典的一个问题啊，通过几个不同的算法求解这一问题，我也总算对该问题有了一定的了解。
实验得分
助教签名
附录：
完整代码（回溯法）
//0-1背包问题回溯法求解
#include
usingnamespacestd;
template
classKnap//Knap类记录解空间树的结点信息
{
template
friendTypepKnapsack（Typep[],Typew[],Typew,int）;
private:
TypepBound（inti）;//计算上界的函数
voidBacktrack（inti）;//回溯求最优解函数
Typewc;//背包容量
intn;//物品数
Typew*w;//物品重量数组¦
Typep*p;//物品价值数组
Typewcw;//当前重量
Typepcp;//当前价值
Typepbestp;//当前最后价值
};
template
TypepKnapsack（Typepp[],Typeww[],Typewc,intn）;//声明背包问题求解函数
template
inlinevoidSwap（Type&a,Type&b）;//声明交换函数
template
voidBubbleSort（Typea[],intn）;//声明冒泡排序函数
intmain（）
{
intn;//物品数
intc;//背包容量
cout<<"物品个数为：
";
cin>>n;
cout<<"背包容量为：
";
cin>>c;
int*p=newint[n];//物品价值下标从1开始
int*w=newint[n];//物品重量下标从1开始
cout<<"物品重量分别为：
"<for（inti=1;i<=n;i++）
{
cin>>w[i];
}
cout<<"物品价值分别为：
"<for（inti=1;i<=n;i++）//以二元组（重量，价值）的形式输出每物品的信息
{
cin>>p[i];
}
cout<<"物品重量和价值分别为：
"<for（inti=1;i<=n;i++）//以二元组（重量，价值）的形式输出每个物品的信息
{
cout<<"（"<}
cout<cout<<"背包能装下的最大价值为：
"<system（"pause"）;
return0;
}
template
voidKnap:
:
Backtrack（inti）
{
if（i>n）//到达叶子节点
{
bestp=cp;//更新最优值
return;
}
if（cw+w[i]<=c）//进入左子树
{
cw+=w[i];
cp+=p[i];
Backtrack（i+1）;//回溯
//回溯结束回到当前根结点
cw-=w[i];
cp-=p[i];
}
//进入右子树，条件是上界值比当前最优值大，否则就将右子树剪掉
if（Bound（i+1）>bestp）
{
Backtrack（i+1）;
}
}
template
TypepKnap:
:
Bound（inti）//计算上界
{
Typewcleft=c-cw;//剩余容量
Typepb=cp;
//以物品单位重量价值递减序装入物品
while（i<=n&&w[i]<=cleft）
{
cleft-=w[i];
b+=p[i];
i++;
}
//如果背包剩余容量不足以装下一个物品
if（i<=n）
{
b+=p[i]/w[i]*cleft;//则将物品的部分装入到背包中
}
returnb;
}
classObject//定义对象类，作用相当于结构体
{
template
friendTypepKnapsack（Typep[],Typew[],Typew,int）;
public:
intoperator>=（Objecta）const//符号重载函数，重载>=符号
{
return（d>=a.d）;
}
private:
intID;//编号
floatd;//单位重量的价值
};
template
TypepKnapsack（Typepp[],Typeww[],Typewc,intn）
{
//为Knap:
:
Backtrack初始化
TypewW=0;
TypepP=0;
Object*Q=newObject[n];//创建Object类的对象数组¦
//初始化Object类的对象数组¦
for（inti=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];
}
if（W<=c）//装入所有物品
{
returnP;
}
//依物品单位重量价值降序排序
BubbleSort（Q,n）;
KnapK;//创建Knap的对象K
K.p=newTypep[n+1];
K.w=newTypew[n+1];
for（inti=1;i<=n;i++）
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
//初始化K
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack
（1）;
delete[]Q;
delete[]K.w;
delete[]K.p;
returnK.bestp;//返回最优解
}
template
voidBubbleSort（Typea[],intn）
{
//记录一次遍历中是否有元素的交换
boolexchange;
for（inti=0;i{
exchange=false;
for（intj=i+1;j<=n-1;j++）
{
if（a[j]>=a[j-1]）
{
Swap（a[j],a[j-1]）;
exchange=true;
}
}
//如果这次遍历没有元素的交换，那么排序结束
if（exchange==false）
{
break;
}
}
}
template
inlinevoidSwap（Type&a,Type&b）//交换函数
{
Typetemp=a;
a=b;
b=temp;
}
升级会员 