回溯法实验.docx

文档介绍：精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
算法分析与设计实验报告
姓名
学号
班级
第工次附加实验
精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
时间
,classTypep>classKnap//Knap类记录解空间树的结点信息{
int);
template<classTypew,classTypep>friendTypepKnapsack(Typep[],Typew[],Typew,private:
TypepBound(inti);〃计算上界的函数voidBacktrack(inti);//回溯求最优解函数Typewc;//包包容量intn;//物品数Typew*w;//物品重量数组Typep*p;//物品价值数组Typewcw;//当前重量
精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
Typepcp;//当前价值
精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
Typepbestp;//当前最后价值};
精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
template<classTypew,classTypep>TypepKnapsack(Typepp[],Typeww[],Typewc,intn);//声明背包问题求解函数template<classType>inlinevoidSwap(Type&a,Type&b);〃声明交换函数template<classType>voidBubbleSort(Typea[],intn);〃声明冒泡排序函数intmain(){
intn;//物品数
intc;//包包容量
cout<<〞物品个数为：〞；
cin>>n;
cout<<"包包容量为：";
cin>>c;
int*p=newint[n];//物品价值下标从1开始
int*w=newint[n];//物品重量下标从1开始
cout<<"物品重量分别为："<<endl;
for(inti=1;i<=n;i++)
(cin>>w[i];
}
cout<<"物品价值分别为："<<endl;
for(inti=1;i<=n;i++)〃以二元组(重量,价值)的形式输出每物品的信息
(cin>>p[i];
}
cout<<〞物品重量和价值分别为："<<endl;
for(inti=1;i<=n;i++)〃以二元组(重量,价值)的形式输出每个物品的信息
(cout<<"("<<w[i]<<","<<p[i]<<")";
精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
}
cout<<endl;
cout<<"背包能装下的最大价值为："<<Knapsack(p,w,c,n)<<endl;//输出结果
system("pause");
return0;
精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
template<classTypew,classTypep>voidKnap<Typew,Typep>::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<classTypew,classTypep>TypepKnap<Typew,Typep>::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;
精品资料，欢迎大家下载！
以上资料仅供参考，如有侵权，留言删除！
c