1 / 8
文档名称:

算法设计背包问题用动态规划的递归实现与非递归实现.doc

格式:doc   大小:94KB   页数:8页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

算法设计背包问题用动态规划的递归实现与非递归实现.doc

上传人:ttteee8 2019/8/10 文件大小:94 KB

下载得到文件列表

算法设计背包问题用动态规划的递归实现与非递归实现.doc

文档介绍

文档介绍::..华南农业大学《算法分析与设计》课程实验专业年级:10信息与计算科学2班学生学号: 22号学生姓名: 梁高鼎实验题目:用动态规划法求解0-1背包问题指导老师:梁茹冰实验时间:012年11月5日一、 实验内容用动态规划法求解0-1背包问题要求:(1)用递归实现(备忘录方法)(2)用非递归实现(动态规划法)二、 、 理解算法思想和问题要求;、 (备忘录方法)voidfind(inti,floattw,floattv){intk;〃物品i包含在当前方案的可能性if(tw+a[i].weight<=limitW){cop[i]=l;if(i<n-l)find(i+1,tw+a[i].weight,tv);else{for(k=0;k<n;++k)option[k]=cop[k];maxv=tv;}}cop[i]=0;〃物品i不包含在当前方案的可能性if(tv-a[i].value>maxv){if(i<n-l)find(i+1,tw,tv-a[i].value);else{for(k=0;k<n;++k)option[k]=cop[k];maxv=tv-a[i].value;(动态规划法)intknapsack(int&n,int&C,ints[M],intp[M],intV[M][M]){inti,j;for(i=0;i<=n;i++)for(j=0;j<=C;j++)if(i==O|[j==O)V[i]|j]=O;elseif(s[i]>j)V[i][j]=V[i-l][j];elseif(s[i]<=j)V[i]U]=max(V[i-l]U],V[i-l][j-s[i]]+p[i]);}returnV[n][C];voidtraceback(intn,intCJnts[M],intx[M],intV[M][M])for(inti=l;i<=n;i++){if(Vfi][C]=V[i-l][C])x[i]=o;elsex[i]=l;C=C-s[i];、 编程实现题忖要求;、 调试程序;、 实验数据及实验结果;:输入数据:背包容量为50公斤。物品1重10公斤,价值60元;物品2重20公斤,价值100元;物品3重30公斤,价值120元。魏入物晶沖数:3输入各初品的重>=102030输入各桝品的价100120輪入限罰重量隔输岀结果::输入数据:背包容量为50公斤。物品1重10公斤,价值60元;物品2重20公斤,价值100元;物品3重30公斤,价值120元。pleaseinputn:3pleaseinputtw:50pleaseinput1102030IpleaseinputV60100120输出结果:、:O(n3):O(n3)三、总结通过本次实验,让我意识到我对编程的不足,但也了解到自己的成长空间还很大。附录:源代码(1)递归实现:#include<>#defineN100〃最大物品总种数intn;//物品总种数floatlimitW;//限制的总重量floatt

最近更新

二零二五年度O2O商家入驻及线上线下融合服务协.. 9页

2025年怎么关闭360安全卫士开机自动启动 2页

2025年怀古的古诗词 9页

2025年鼻咽癌解剖学应用研究要点 35页

二零二五个人对公司的大额资金借款合同 8页

中年夫妻2025年度离婚协议及共同财产清算执行.. 8页

个人车位出租合同2025年度范本解析与修订 7页

个人住宅外墙防水补漏及修缮施工协议 8页

2025年快乐学习的励志演讲稿 8页

2025年忠心对党心得体会 5页

2025年志愿者活动策划方案大全 18页

2025年度高速铁路建设工程劳务承包合同 9页

2025年度高端自动门安装与维护服务合同 9页

2025年心理咨询师三级考试技巧详情 5页

2025年度高端办公设备采购与技术支持服务合同.. 9页

短期商务汽车租赁合同之三 5页

2025年度高空作业外架承包合同本 9页

2025年重症监护室常用监测技术盘点 90页

2025年度高科技企业临时场地租赁服务合同 9页

2025年度高新技术公司资产转让合同 9页

2025年度高新技术企业人员派遣合作协议书 8页

2025年度高效协同劳务人工承包协议 8页

2025年超声引导神经阻滞麻醉技术解析 70页

2025年微笑为题的小学三年级作文 9页

白酒定制合同 6页

畜牧设备采购合同书 6页

2025年徐文长传文言文答案 6页

2025年工程竣工自评报告三篇 19页

XX学校义务教育优质均衡发展创建实施方案范文.. 8页

顺丁烯二酸酐工艺规程 25页