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

最近更新

2025年度市政绿化苗木栽植与生态平衡合同 9页

2025年度家庭私人家教定制方案合同 9页

酸碱催化剂及其催化作用 47页

2025年度大数据分析服务比例分成合同 8页

2025年度城市核心地段手房租赁承包管理协议 9页

酒店投诉处理技巧培训 84页

2025年度员工综合素质教育培训服务合同 9页

2025年度厂房拆除与建筑废弃物环保处理技术研.. 10页

2025年度医师医疗信息安全管理聘用合同 8页

2025年度分手协议书模板:分手后共同债务承担.. 8页

2025年度农产品快速配送道路运输服务合同 10页

2025年度公司合规管理及法律事务处理合作协议.. 11页

2025年度健康养生中心会员服务合同简易版 8页

最新个人租房合同范本 7页

2025年度企业培训与人才发展服务合同 9页

部分电子表格处理 89页

2025年度乡村旅游用地转让承包管理协议 9页

智能制造设备技术合作合同(第一部分) 6页

遗传病和人类健康 28页

新版劳动合同的四大法律特征解析 6页

新房交付质量保证金补充合同 5页

散货及快件出口运输代理合同范本 6页

教师岗位的劳动合同范本 7页

政府债券债务转让合同全文 6页

文化创意产品海运合同范本3篇 50页

轮胎式工程机械驱动桥 38页

教育玩具物流交易协议3篇 51页

教育大厦装修合同模板3篇 55页

教育培训企业股权居间合同3篇 49页

教学楼装修解除通知书3篇 53页