2025年动态规划习题完整版 .pdfVIP

为天地立心，为生民立命，为往圣继绝学，为万世开太平。——张载

动态规划习题

Documentserialnumber【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】

英雄者，胸怀大志，腹有良策，有包藏宇宙之机，吞吐天地之志者也。——《三国演义》

动态规划专题分类视图

数轴动规题：

题1.2001年普及组第4题--装箱问题

【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0n≤30),每

个物品有一个体积（正整数）。要求从n个物品中,任取若干个装入箱内,使箱子的剩余

空间为最小。

【输入格式】输入文件box.in有若干行。第一行：一个整数，表示箱子容量V；

第二行：一个整数，表示物品个数n；接下来n行，分别表示这n个物品的各自体积。

【输出格式】输出文件box.out只有一行数据，该行只有一个数，表示最小的箱子剩余

空间。

【输入样例】

24

6

8

3

12

7

9

7

【输出样例】

0

题2.1996年提高组第4题--砝码秤重__数据加强版

【问题描述】设有n种砝码,第k种砝码有C个,每个重量均为W,求：用这些砝码能秤

kk

出的不同重量的个数，但不包括一个砝码也不用的情况。

【输入格式】输入文件weight.in的第一行只有一个数n,表示不同的砝码的种类数.

第2行至第n+1行,每行有两个整数.第k+1行的两个数分别表示第k种砝码的个数和重

量.

【输出格式】输出文件weight.out中只有一行数据:Total=N。表示用这些砝码能秤出

的不同重量数。

【输入样例】

2

22

23

【输出样例】

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≤400000;

题3.石子归并-szgb.pas

【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使

两堆质量的差最小。

【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。接下

去的n行,为每堆石子质量。

【输出】输出文件szgb.out的只有一行,该行只有一个整数,表示最小的质量差.

【样例输入】

5

5

8

13

27

14

【样例输出】

3

题4.补圣衣

【问题描述】有四个人，每人身上的衣服分别有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)

【输