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页

2025年度深圳数字经济产业劳动合同规范 9页

2025年度汽车销售代签合同授权委托售后服务合.. 8页

2025年度汽车制造人事代理聘用服务协议 9页

2025年度残疾人事业帮扶协议书范本汇编 9页

2025年度智能社区安防监控系统维护保养服务协.. 9页

2025年度智能机器人核心专利技术授权及转让合.. 8页

2025年度智能家居设备个人信息采集及授权协议.. 7页

2025年度智能家居产品销售及安装服务合同 9页

2025年度智能停车系统停车位使用权转让协议 8页

2025年度智慧能源管理系统供货合同集合 9页

主生产计划和MRP计划计算 64页

2025年度智慧养老业主物业服务综合服务合同 8页

2025年度施工现场安全责任保险赔偿协议 8页

2025年度新能源基金份额代持与政府补贴对接合.. 8页

2025年度新材料研发合伙退伙协议书版 8页

2025年度文化艺术合同经理工作规范与版权保护.. 8页

2025年度教育机构员工劳动合同规范协议书 8页

2025年度教育培训居间合同简易执行 9页

2025年度手车共享出行平台合作协议 9页

2025年度房产中介房屋买卖绿色建筑推广合同 9页

2025年度影视剧组安全监督聘用合同 9页

临床合理用药培训 65页

2025年度广东省房屋租赁合同示范文本制作合同.. 8页

2025年度幼儿园安保服务聘用合同书实施细则 8页

艺术舞蹈老师简历模板 1页

服装设计合作协议书 5页

全国学前教育普及普惠区创建工作方案 5页

煤炭资源地质勘查设计编写提纲 14页