回溯法 背包问题.docx
- 文档编号:10290989
- 上传时间:2023-05-24
- 格式:DOCX
- 页数:8
- 大小:51.18KB
回溯法 背包问题.docx
《回溯法 背包问题.docx》由会员分享,可在线阅读,更多相关《回溯法 背包问题.docx(8页珍藏版)》请在冰点文库上搜索。
回溯法背包问题
摘要
回溯法是算法设计的基本方法之一,又称“通用解题法”。
使用回溯法可以系统地搜索所给问题的一个解或全部解。
它适用于求解一些涉及到寻找一组解的问题或者求满足某些约束条件的最优解问题,且适用于求解组合数量较大的问题。
行业、各领域都广泛采用了计算机信息技术,并由此产生出开发各种应用软件的需求。
为了以最小的成本、最快的速度、最好的质量开发出适合各种应用需求的软件,必须遵循软件工程的原则。
设计一个高效的程序不仅需要编程小技巧,更需要合理的数据组织和清晰高效的素算法,这正是计算机科学领域数据结构与算法设计所研究的主要内容。
因此,了解回溯法的基本思想与解题步骤对解决结合0-1背包问题介绍了回溯法的基本思想和解题步骤,并在C++6.0环境下验证了回溯法可以有效地解决0-1背包问题。
关键词:
回溯法,背包问题
目录
1问题描述1
2问题分析2
3建立数学模型3
4算法设计4
5算法实现5
6测试分析8
结论9
参考文献10
1问题描述
对于0-1背包问题回溯法的一个实例,n=4,c=7,p=[9,10,7,4],w=[3,5,2,1].这4个物品的单位重量价值分别为[3,2,3,5,4].以物品为单位价值的递减序装入物品。
先装入物品4,然后装入物品3和1.装入这3个物品后,剩余的背包容量为1,只能装入0.2的物品2.由此可得到一个解为x=[1,0,2,1,1],其相应的价值为22.尽管这不是一个可行解,但可以证明其价值是最有大的上界。
因此,对于这个实例,最优值不超过22.回溯法的基本思想是按深度优先策略,从根节点出发搜索解空间树,算法搜索至解空间的任一点时,先判断该结点是否包含问题的解,如果肯定不包含,则跳过以该结点为根的子树的搜索,逐层向其祖先结点回溯,否则,进入该子树,继续按深度优先进行搜索。
2问题分析
利用回溯法的设计思想来解决背包问题。
首先是将可供选择的物品的个数输入程序,将物品排成一列,计算总物品的体积s,然后输入背包的实际体积V,如果背包的体积小于0或者大于物品的总体积s,则判断输入的背包体积错误,否则开始顺序选取物品装入背包,假设已选取了前i件物品之后背包还没有装满,则继续选取第i+1件物品,若该件物品"太大"不能装入,则弃之而继续选取下一件,直至背包装满为止。
但如果在剩余的物品中找不到合适的物品以填满背包,则说明"刚刚"装入背包的那件物品"不合适",应将它取出"弃之一边",继续再从"它之后"的物品中选取,如此重复,直至求得满足条件的解。
因为回溯求解的规则是"后进先出",所以要用到栈来存储符合条件的解,在存储过程中,利用数组来存储各个物品的体积,然后用深度优先的搜索方式求解,将符合条件的数组元素的下标存入栈里,最后得到符合条件的解并且实现输出。
3建立数学模型
0-l背包问题是子集选取问题。
一般情况下,0-1背包问题是NP难题。
0-1背包问题的解空间可用子集树表示。
解0-1背包问题的回溯法与装载问题的回溯法十分类似。
在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。
当右子树有可能包含最优解时才进入右子树搜索。
否则将右子树剪去。
设r是当前剩余物品价值总和;cp是当前价值;bestp是当前最优价值。
当cp+r≤bestp时,可剪去右子树。
计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背包。
由此得到的价值是右子树中解的上界。
算法复杂性是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性,需要的空间资源的量称为空间复杂性。
这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。
如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身,而且用C表示复杂性,那么,应该有C=F(N,I,A)。
一般把时间复杂性和空间复杂性分开,并分别用T和S来表示,则有:
T=T(N,I)和S=S(N,I)。
最坏情况下的时间复杂性:
最好情况下的时间复杂性:
平均情况下的时间复杂性:
其中DN是规模为N的合法输入的集合;I*是DN中使T(N,I*)达到Tmax(N)的合法输入;是中使T(N,)达到Tmin(N)的合法输入;而P(I)是在算法的应用中出现输入I的概率。
4算法设计
使用栈作为该程序的数据结构,利用栈进行语法检查,以深度优先的搜索方式解空间,实现递归过程和函数的调用,在设计时还使用C语言的数组及其循环语言来实现程序。
运用回溯法解题,在搜索解空间树时,只要其左儿子节点是一个可行结点,搜索就进入左子树,在右子树中有可能包含最优解是才进入右子树搜索。
否则将右子树剪去。
具体步骤如下:
1.针对所给问题,定义问题的解空间;
2.确定易于搜索的解空间结
3.以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索;
5算法实现
运用Pc机,C/C++程序学习系统软件编程C语言
程序源代码
#include
#definesize20
structstacks
{
intdata[size];
inttop;
}stack;
voidmain()
{
intw[size];
intV;
intk=0;
inti=0;
intj=1;
intnumber;
ints=0;
printf("\n请输入可供选择装入物品的个数:
");
scanf("%d",&number);
printf("\n请输入各件物品的体积:
");
for(i=0;i scanf("%d",&w[i]); for(i=0;i s=s+w[i]; printf("\n可供选择的物品的总体s=%d\n",s); printf("\n请输入背包的总体积: "); scanf("%d",&V); if(V<0||V>s) printf("\n输入背包体积错误"); printf("\n"); for(i=0;i stack.data[i]=0; stack.top=0; do { while(V>0&&k<=number) { if(V>=w[k]) { stack.data[stack.top]=k; stack.top++; V-=w[k]; } k++; } if(V==0) { printf("第%d个符合条件的解: ",j); for(i=0;i { printf("%d",w[stack.data[i]]); } j++; printf("\n"); } k=stack.data[--stack.top]; stack.data[stack.top]=0; V+=w[k]; k++; }while(! (stack.top==0&&k==number)); } 6测试分析 1.当输入的背包体积V小于物品的总体积s时: 2.当输入的背包体积V大于物品的总体积s时: 当输入的背包体积小于等于可供选择的物品的总体积时,可以正确进行选择装入的物品,并且统计符合条件的解的方法;当输入的背包体积小于0或者大于可供选择的物品的总体积时,程序会自动提醒输入背包体积错误,这样就方便了程序的正确运行与解决实际问题的重要作用。 图6.1 图6.2 结论 本程序利用回溯法的设计思想来解决问题,在用来求问题的所有解时,针对所给问题,定义问题的解空间,确定易于搜索的解空间结构,要回溯到根,且根结点的所有子树都已被搜索遍才结束,回溯法的求解规则是后进先出,所以在程序设计中自然要使用到了栈。 在程序设计过程中,更加巩固了我的C语言程序设计基础知识,使我对C语言的循环操作和指针、数组操作更加熟悉,区别了栈与链表,学会用栈来解决实际问题,并且联系了树的重要内容,重点训练了对算法与数据结构的难点内容,算法与数据结构的统一,使编程语言更加简洁,清晰易懂,强调了好的程序设计风格,运行结果更加美观,在调试和运行时,我遇到了一些很基础的问题,通过请教老师和同学,这些问题都逐一解决了,这使得我在运行正确通过时,内心产生了一种很强烈的成就感,因此提高了我对编程的浓厚兴趣,更加增强了自己学习好计算机语言的信心。 参考文献 [1]黄迪明,余勤等编著. C语言程序设计教程[M].国防工业出版社1999. [2]陈媛等编著. 算法与数据结构[M]. 清华大学出版社2002. [3]王晓东编著.计算机算法设计与分析[M].北京: 电子工业出版社,2007.5 [4]余祥宣,崔国华,邹海明.计算机算法基础[M].武汉: 华中科技大学出版社,2000. [5]卢开澄.计算机算法导引—设计与分析[M].北京: 清华大学出版社,2003. [6]M.H.ALSUWAIYEL.算法设计技巧与分析[M].北京电子工业出版社.2006.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 回溯法 背包问题 回溯 背包 问题
![提示](https://static.bingdoc.com/images/bang_tan.gif)