文档介绍：动态规划专题分类视
数轴动规题：
题 年普及组第4 题 -- 装箱问题
【问题描述】有一个箱子容量为 V（正整数，0W" 20000）,同时有n个物品（0<n < 30）,每个物品有一个 体积（正整数） 。要求从 n 个; 接下来 n 行，每行两个数字，分别是ti 和 pi ，两个数字之间用一
个空格分开。
【输出】 只包含一行，该行只有一个数字，代表了光光最少受到的批评。
【样例输入】
5
3
26
13
47
【样例输出】
6
【数据规模约定】
100%勺数据中,k & 100000,ti & 10000,pi & 10000;
30%勺数据中,n <20;
100%勺数据中,n < 500;
题 7. 打包 [/]2006 年 OIBH 新年赛
【问题描述】你现在拿到了许多的礼物，你要把这些礼物放进袋子里。你只有一个最多装下 V 体积物
品的袋子，你不能全部放进去。你也拿不动那么重的东西。你估计你能拿的最大重量为Go现在你了
解了每一个物品的完美值、重量和体积，你当然想让袋子中装的物品的完美值总和最大，你又得计划
一下了。
【输入】
第一行：G 和 V 表示最大重量和体积。
第二行：N 表示拿到 N 件礼物。
第三到N+2行：每行3个数TiGiVi表示各礼物的完美值、重量和体积
【输出】
输出共一个数，表示可能获得的最大完美值。
【输入输出样例】
输入 () ：
65
4
1022
2032
4043
3033
输出 () ：
50
【数据范围】
对于20%勺数据N,V,GTi,Vi,Gi< 10
对于50%勺数据N,V,GTi,Vi,Gi< 100
对于80%勺数据N,V,GTi,Vi,Gi < 300
80唯ij 100%勺数据是N, V,G,Ti,Vi, Gi w 380的离散随机数据。
较复杂的数轴动规
-同济ACMB 1132题
Problem小卡卡终于帮农夫 John找到了走丢的那一头奶牛，John为了感谢小卡卡，不仅告诉了他在
Pascal山脉上可能存在 Pascal圣地最大的宝藏，还说要请小卡卡喝牛奶。可是农夫John发现他 家里所储藏的牛奶已经喝光了 ，所以要临时给奶牛挤奶。小卡卡实在是太好心了，说要帮农夫John 一
起挤牛奶。John答应了，他把他的n头奶牛中的n/2头（n是个偶数）分给小卡卡挤，他自己挤剩下 的n/2头奶牛。但是每一头奶牛都有不同的产奶量，农夫John为了让小卡卡减轻负担，他希望他们两
个所挤的牛奶的总量之差最小。小卡卡得知了每头奶牛的产奶情况之后很快就解决了这个问题。 Input 测试数据第一行一个整数n, n为偶数且小于100。表示有n头奶牛。
第二行n个整数分别给出每头奶牛的产奶量（产奶量的总和不超过2000）。
Output 输出小卡卡和农夫所挤的牛奶量的最小差值。
SampleInput 6 792642 SampleOutput 0 题8. 一般性的最少硬币组成问题 从n种币值为a[1..n]的硬币中，任选几个硬币组成价值为V的一堆货币，问最少需要几个硬币？其中每
种硬币的数量没有限制。1<=n<=100,1<=v<=100000,1<=a[i]<=100000
：第一行有两个数 v和n;第二行有n个以空格分隔的数，表示n个币值. ，该行只有一个数，表示所需的最少硬币数，如果无论如何选取硬 币，均不能得到币值v,则输出0. 已知第j个公司使用k台机器时，能得到的利润为a[j,k],问如何将m台机器在n个公司中分配，才能 获得最大利润？ 2个公司能获得的盈利情况如
下：
公司号机器数
1
2
3
1
2
3
4
2
1
4
5
最大盈利为6,方案为公司2使用2台，公司1使用1台.
---（）
小XC发现垒城堡的时候，如果下面的积木比上面的积木大，那么城堡便不易倒。所以他在垒城堡的时 候总是遵循这样的规则。小XC想把自己垒的城堡送给幼儿园里同学们，这样可以增加他的好感度。
为了公平起见，他决定把送给每个同学一样高的城堡，这样可以避免同学们为了获得更漂亮的城堡而 引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要