动态规划专题分类视图数轴动规题: 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转载请标明出处.