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

最近更新

二零二五年度事业单位公共卫生人员人事聘用合.. 8页

2025年冠心病基层防治攻略 29页

二零二五年度临时小时工劳动合同(家政服务专.. 9页

二零二五年度个体诊所聘用合同书:诊所中医馆.. 8页

2025年愚人节欢乐恶搞方法 愚人节恶搞整人要点.. 3页

2025年儿童过敏性紫癜肾炎治疗攻略 59页

2025年惊蛰的寓意与含义是什么 4页

2025年惊涛骇浪观看心得总结 8页

二零二五年度个人旅游服务对赌预订合同 9页

二零二五年度个人护理产品促销服务合同 9页

2025年儿童常用药物与特效药指南 22页

二零二五年度个人土地使用权买卖协议 9页

2025年儿童出疹症状家庭护理攻略 49页

2025年怎样饲养一岁的泰迪犬 7页

二零二五年度个人二手车买卖合同范文 8页

二零二五年度业绩承诺协议:智能家电研发与销.. 9页

二零二五年度不交社保艺术品鉴定劳务合同范本.. 9页

二零二五年度上海劳动合同解除赔偿标准与劳动.. 8页

2025年怎么写考试心得简单的 48页

二零二五年度三人合伙光伏发电项目合作协议书.. 9页

二零二五年份家禽产业绿色发展合作协议 9页

二零二五家庭光伏电站屋顶租赁与电力储备合同.. 9页

2025年H7N9禽流感预防攻略 25页

2025年快速提高文科成绩的方法 6页

工程质量控制中试验检测的重要性 24页

2级经销商分销协议 5页

2024年高中生情绪调控心得体会(热门24篇) 36页

【2023年】福建省龙岩市辅警协警笔试笔试真题.. 16页

村后备干部笔试试题A及答案(最新版) 12页

物理学英文论文 4页