下载此文档

动态规划习题.doc


文档分类:高等教育 | 页数:约26页 举报非法文档有奖
1/26
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/26 下载此文档
文档列表 文档介绍
动态规划专题分类视图数轴动规题: 1较复杂的数轴动规 4线性动规 7区域动规: 14未知的动规: 20数轴动规题:--装箱问题 【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0<n≤30),每个物品有一个体积(正整数)。要求从n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。【输入格式】。第一行:一个整数,表示箱子容量V;第二行:一个整数,表示物品个数n;接下来n行,分别表示这n个物品的各自体积。【输出格式】,该行只有一个数,表示最小的箱子剩余空间。【输入样例】2468312797【输出样例】--砝码秤重__数据加强版【问题描述】设有n种砝码,第k种砝码有Ck个,每个重量均为Wk,求:用这些砝码能秤出的不同重量的个数,但不包括一个砝码也不用的情况。【输入格式】,+1行,+1行的两个数分别表示第k种砝码的个数和重量.【输出格式】:Total=N。表示用这些砝码能秤出的不同重量数。【输入样例】22223【输出样例】Total=8【样例说明】重量2,3,4,5,6,7,8,10都能秤得【数据限制】对于100%的数据,砝码的种类n满足:1≤n≤100;对于30%的数据,砝码的总数量C满足:1≤C≤20;对于100%的数据,砝码的总数量C满足:1≤C≤100;对于所有的数据,砝码的总重量W满足:1≤W≤; - 【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。 【输入】(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。【输出】,该行只有一个整数,表示最小的质量差.【样例输入】558132714【样例输出】【问题描述】有四个人,每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示(A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损,只能是同一件衣服上的。就是说你只能同时修补一件衣服,修好了,才能修补下一件。【输入】本题包含5行数据:第1行,为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20)第2行,为A1...As1共s1个数,表示第一件衣服上每个破损修好它所需的时间第3行,为B1...Bs2共s2个数,表示第二件衣服上每个破损修好它所需的时间第4行,为C1...Cs3共s3个数,表示第三件衣服上每个破损修好它所需的时间第5行,为D1...Ds4共s4个数,表示第四件衣服上每个破损修好它所需的时间(1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60)【输出】输出一行,为修好四件衣服所要的最短时间。【样例输入】1213 5436243【样例输出】 【问题描述】光光上了高中,科目增多了。在长假里,光光的老师们都非常严厉,都给他布置了一定量的作业。假期里,光光一共有的时间是k小时。在长假前,老师们一共给光光布置了n份作业,第i份作业需 要的时间是ti小时。但是由于老师们互相不商量,因此光光有可能不能完成老师的作业。当不能完成老师的作业时,光光就事后去向老师说明,然后被老师批评一顿了事。对于一件作业,只有2种情况:完成或者不完成(快要完成也算不完成)。如果没完成,受到批评是天经地义的。但是,不同的作业对于光光来说,批评的力度是不同的。第i件作业如果没完成,就要受到pi个单位的批评。多次这样之后,光光想要在长假前就知道他至少会受到多少个单位的批评。你能帮助他吗?【输入】:第一行只有一个数字k,表示光光一共有的时间数;第二行只有一个数字n,表示作业数;接下来n行,每行两个数字,分别是ti和pi,两个数字之间用一个空格分开。【输出】,该行只有一个数字,代表了光光最少受到的批评。【样例输入】53261347【样例输出】6【数据规模约定】100%的数据中,k≤,ti≤10000,pi≤10000;30%的数据中,n≤20;100%的数据中,n≤500;[/]2006年OIBH新年赛【问题描述】你现在拿到了许

动态规划习题 来自淘豆网m.daumloan.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数26
  • 收藏数0 收藏
  • 顶次数0
  • 上传人gxngqvk
  • 文件大小140 KB
  • 时间2020-08-28