输入关键词搜索资料
分享
首 页
个人中心
意见反馈
帮助中心
首页 >
高等教育 >
教育学
背包问题ppt课件
2021-02-25
16页
ppt
314KB
64阅读
爱赢
公司经营范围:网络软件设计、制作、图文设计、影视制作(编辑)
举报
背包问题ppt课件背包问题有一个贼在偷窃一家商店时发现有n件物品:第i件物品值vi元,重wi磅,(1≤i≤n),此处vi和wi都是整数。他希望带走的东西越值钱越好,但他的背包中最多只能装下m磅的东西(m为整数)。有两种偷窃方式:1.01──背包问题如果每件物品或被带走或被留下,小偷应该带走哪几件东西?2.部分背包问题如果允许小偷可带走某个物品的一部分,小偷应该带走哪几件东西,每件东西的重量是多少?.采用贪心策略来解决部分背包问题:⑴对每件物品计算其每磅价值vi/wi⑵按每磅价值单调递减的顺序对物品排序。例如,总共有三件物品和一个背包 开始时对...
背包问
题
快递公司问题件
快递公司问题件货款处理
关于圆的周长面积重点题型
关于解方程组的题及答案
关于南海问题
有一个贼在偷窃一家商店时发现有n件物品:第i件物品值vi元,重wi磅,(1≤i≤n),此处vi和wi都是整数。他希望带走的东西越值钱越好,但他的背包中最多只能装下m磅的东西(m为整数)。有两种偷窃方式:1.01──背包问题如果每件物品或被带走或被留下,小偷应该带走哪几件东西?2.部分背包问题如果允许小偷可带走某个物品的一部分,小偷应该带走哪几件东西,每件东西的重量是多少?.采用贪心策略来解决部分背包问题:⑴对每件物品计算其每磅价值vi/wi⑵按每磅价值单调递减的顺序对物品排序。例如,总共有三件物品和一个背包 开始时对具有每磅价值最大的物品尽量多拿一些。如果拿完了该物品算法:begin⑴读入数据;⑵计算物品的单位重量价值Ti=vi/wi,并将它们从大到小排序;⑶依次选择单位价值较大的物品装入背包,直至不能装入;⑷输出最大价值总和s和装货方案;end;后仍可以取一些其他物品时,再取具有每磅价值次大的物品,一直继续下去,直到不能取为止..部分背包问题中,在考虑是否把一件物品加到背包中时,不需要把加入该物品的子问题解与不取该物品的子问题解加以比较。由这种贪心方式所形成的所有子问题是互相独立的。若对0-1背包问题采取贪心策略,顺序取物品1和2 在0-1背包问题中不应取物品1的原因在于这样无法将背包填满,空余的空间降低了它的每磅价值,因此当我们考虑是否要把一件物品加到背包中时,必须对把加进该物品的子问题的解与不取该物品的子问题的解进行比较。由这种方式形成的子问题导致了许多重迭的子问题。对于这一类虽具有最优化结构性质、但产生的子问题互为重迭的试题,一般采用动态程序设计的方法求解。最优解取的是物品2和3,没有取物品1。两种包含物品1的可能解都不是最优解 .01年初4装箱问题:一箱的容量为V(0
要求
对教师党员的评价
套管和固井
爆破片与爆破装置
仓库管理基本要求
三甲医院都需要复审吗
从n个物品中,任取若干个装入箱内,使剩余空间为最小。样例:输入:24 {
表
关于同志近三年现实表现材料
材料类招标技术评分表
图表与交易pdf
视力表打印pdf
用图表说话 pdf
箱子容量} 6 {n个物品} 8 3 12 7 9 7 输出:0 {表箱剩余空间}讨论:阶段?状态?决策?状态转移?可取的物品有i个能组成的各种体积加入i能组成满足条件的体积(取、不取)f[i]=max{f[j]+w[i]|取i}j
=tt[j])then{若第j种药的采取时间小于i,则考察j药}begin{决策}b:=dp[i-tt[j],j-1]+vv[j];{在已用(i-tt[j])时间,采(j-1)药时,又取第j种药}if(b>a)thena:=b;enddp[i,j]:=a;end;end;writeln(dp[t,m]);end.用动规求解:.第 2 题 快乐的金明 ( happy.pas/c/cpp )【问题描述】金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1~5表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1,j2,……,jk,则所求的总和为:v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。(其中*为乘号)请你帮助金明设计一个满足要求的购物单。.【输入文件】输入文件happy.in 的第1行,为两个正整数,用一个空格隔开:N m(其中N(<30000)表示总钱数,m(<25)为希望购买物品的个数。)从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有2个非负整数v p(其中v表示该物品的价格(v<=10000),p表示该物品的重要度(1~5))【输出文件】输出文件happy.out只有一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。【输出样例】3900购第2、3、5件物品【输入样例】1000 51000元钱,有5件物品供选择800 2第1件物品,价800,重要度为2400 5第2件物品,价400,重要度为5300 5400 3200 2第5件物品,价200,重要度为2第 2 题 快乐的金明 ( happy.pas/c/cpp ).【输入样例】1000 5800 2400 5300 5400 3200 2【输出样例】3900【算法分析】本题考察的是基本的01背包问题,当然搜索也可以做全对,数据量太大了。ij1、以物品为阶段i2、以所用费用为状态j3、以取乘积最大为决策4、状态转移a[i,j]:考察了i种物品,用去j钱的最大乘积w[i]:第i种物品重p[i]:第i种物的价值a[i,j]:=max{a[i-1,j],a[i-1,j-w[i]]+w[i]*p[i]}a第 2 题 快乐的金明 ( happy.pas/c/cpp ).【输入样例】1000 5800 2400 5300 5400 3200 2【输出样例】3900ijfori:=1tokdo{以物品为阶段i}begin{以所用费用j为状态}forj:=1tow[i]-1doa[i,j]:=a[i-1,j]{用j钱买不到i物品}forj:=w[i]tondo{用j钱可买到i物品}ifa[i-1,j]
= p [ i ] ) and( g [ i - 1 , j - p [ i ] ] + w [ i ] > g [ i - 1 , j ] ){决策}Then g [ i , j ] := g [ i - 1 , j - p [ i ] ] + w [ i ]{选取i物品} Else g [ i , j ] := g [ i - 1 , j ] ;{不选取i物品} Writeln ( g [ m , n ] )1000 5800 2400 5300 5400 3200 2【输出样例】3900pwijgg [ i , j ]:已考察到第i个物品,费用为j的所选物的价格与重要度的乘积的最大总和.varp:array[0..30000]oflongint;i,j,w,v,m,n:integer;beginreadln(n,m);{读入钱数n,物品数m}fori:=1tomdo{以物品为阶段}beginreadln(v,w);{读入费用v重要度w}forj:=ndowntovdo{以总费用n为状态}if(v*w+p[j-v]>p[j]){决策:当前用j费用,考察到第i个物品的最大乘积}thenp[j]:=v*w+p[j-v];end;writeln(p[n]);end..vara:array[-1..10,-1..2000]oflongint;w,p,c:array[1..10]oflongint;m,n,i,j,k:integer;beginread(n,m);m:=5;fillchar(a,sizeof(a),0);fori:=1tomdobeginread(w[i],p[i]);c[i]:=w[i]*p[i];end;fori:=1tomdobeginforj:=1tow[i]-1doa[i,j]:=a[i-1,j];forj:=w[i]tondoifa[i-1,j]
/
本文档为【背包问题ppt课件】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
相关资料
药用(PVC)硬片和药品包装用铝箔
2018考研英语翻译每日一文:颐和园
高校体育课程以赛促教教学模式创新与实践
五年级阅读练习题
教育是温暖的课件
sony PSP1000 摔过不读卡故障的维修(附拆机过
英语欢迎标语
合约经济学
主墩钢板桩围堰施工费用预算
小学四年级音乐教学学期工作总结
电脑知识强化班_系统_125_宽带安装和使用问题集粹
平静的生活——婚礼详细策划方案
中国比内测验
虎林第四届全运会逸夫中学优秀运动员名单
2014浙江高考理综化学第8题选择题:实验化学
现代汉语修辞学
私人卖房协议样本图
海地软件使用方法大全
国土资源部关于印发《关于加强土地资产管理促进国有企业改革和发展的若干意见》的通知(国土资发〔1999〕43
欧美、日韩歌曲合集
热门搜索
VTK-Designer使用手册
《财务管理学—荆新》PPT教案模板
变配电站(室)安全检查表
2020年大学英语四级
幼儿园古诗风的教学设计和教学反思
教学故事 小娟就像亲姐妹,形影不离。有一位初二的女学生(小梅),跟我班的美玲也不知为什么
(2008年泰州市)20用锤子以相同的力将铁钉垂直钉入木块...
商贸(仓储)企业安全生产隐患排查治理体系方案全套资料(2021-2022完整版)
全国营造林实绩综合核查工作规范及核查办法
柬埔寨铝矿市场开采与矿权投资前景预测报告
房地产企业会计报表附注内容
市场营销学课后习题与答案
事业单位年度评优方案
端午节的所有小故事
VTK-Designer使用手册
《财务管理学—荆新》PPT教案模板
变配电站(室)安全检查表
2020年大学英语四级
幼儿园古诗风的教学设计和教学反思
教学故事 小娟就像亲姐妹,形影不离。有一位初二的女学生(小梅),跟我班的美玲也不知为什么
(2008年泰州市)20用锤子以相同的力将铁钉垂直钉入木块...
商贸(仓储)企业安全生产隐患排查治理体系方案全套资料(2021-2022完整版)
全国营造林实绩综合核查工作规范及核查办法
柬埔寨铝矿市场开采与矿权投资前景预测报告
房地产企业会计报表附注内容
市场营销学课后习题与答案
事业单位年度评优方案
端午节的所有小故事
你可能还喜欢
单片机课后习题解答
五台山秘传-手相绝对符4
【部编人教版】九年级语文下学期期中试卷(有答案) (9)
2023年宁夏回族自治区银川市兴庆区唐徕回民中学八年级数学第二学期期末考试模拟试题含解析
2018部编人教版语文三年级上册第2课《花的学校》第1课时|课件(共9张PPT)
平行四边形性质说课稿
泰索帝版说明书
东风4D型内燃机车电气试验程序及故障判断
华中科技大学电路试卷
古诗木兰者,古时一民间女子也翻译赏析
漏洞扫描技术PPT课件
来料检验报告表格
天津市业主大会和业主委员会活动规则
80后新人打造创意十足的个性婚纱照风格 Microsoft Word 文档 (3)
中海地产 高端项目精装修技术要求
餐前试吃记录
三年级家长会班主任发言稿
三年级家长会班主任发言稿
三年级家长会班主任发言稿
三年级家长会班主任发言稿
最新资料
资料动态
专题动态
搜索
热门搜索
离婚协议书
入党申请书
房屋租赁合同
贫困申请书
历史搜索
清空历史搜索