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年度金融科技项目提成合同 10页

2025年度酒店客房预订旅游住宿预订代理服务协.. 9页

2025年度道路救援服务设施租赁合同 10页

第l六章铁公路运输gai 52页

2025年度跨境电商平台入股合伙人协议书 9页

2025年度货运驾驶员团队建设与雇佣合同 7页

钢筋混凝土梁板结构(IV) 53页

2025年度菲迪克合同条件应用解析与建筑合同争.. 9页

2025年度花卉展会专用花卉采购合同 10页

2025年度航空航天散热器铝合金采购合同简易版.. 10页

2025年度脚手架租赁与安全防护设施配套合同 10页

2025年度股东合作推进人工智能产业发展合同 7页

2025年度老年人就业权益维护劳务协议书 9页

2025年度网络安全防护技术合作框架协议 9页

2025年度绿色能源项目年劳动合同书 7页

2025年度绿色建筑工地民工劳动保障服务合同 9页

2025年度纱窗产品展示与销售活动策划合同协议.. 8页

2025年度税务筹划与税务筹划改进合同 11页

第九章国际化企业的总体经营战略 45页

2025年度生鲜超市加盟连锁管理服务合同 8页

2025年度生态修复工程融资服务合同 8页

2025年度环保设备采购合同汇编 10页

2024年《行测》国考真题(地市级) 56页

2025年度游乐场设施设备安全保险合同 10页

2025年度消防工程消防水池安全防护设施合同 9页

2025年度洒水车购置与高速公路路面清洁服务合.. 10页

2025年度汽车维修企业安全生产责任合同 8页

2025年度水稻收购与市场风险对冲合同模板 10页

2025年度正规物业管理劳务合同书 9页

2025年度智能设备研发企业员工借调与技术转移.. 8页