主题：[经典的算法题分享][原创]高手是怎样练成的---30天搞定最经典的算法训练题（每天必做,不断更新)
vcacm
[专家分：1500] 发布于 2007-04-29 14:00:00
[color=0000FF]
由于本人最近准备全身心地投入算法学习研究中，幸运地是我买到了一本好书，里面有最经典的算法！
特别是其中的题目，可为是经典中的“精华”，我想把其中的训练题贴上来和大家一起分享！
我准备花一个多月的时间把它们搞定，所以我会把我做出来的题目的解答贴在后面！
同时我也希望大家能把自己做出来了的题目的解答贴上来一起交流！争取找到更好算法！
[/color]
[code]
Algorithm Experiment Problem Set
Xiaodong Wang
(wangxd@fzu.edu.cn)
Department of Computer Science
Fuzhou University P.R.China
February, 2006
[color=FF00FF]Chapter 1 Introduction[/color]
Problem 1.1 Counting
Problem 1.2 Dictionary
Problem 1.3 Divisors
Problem 1.4 Coin Array
Problem 1.5 Maximum Gap
[color=FF00FF]Chapter 2 Recursion and Divide and Conquer[/color]
Problem 2.1 Pipeline
Problem 2.2 Majority
Problem 2.3 Post Office
Problem 2.4 Knight’s Hamilton Tour
Problem 2.5 Half Multiset
Problem 2.6 Half Set
Problem 2.7 Soldiers
Problem 2.8 Permutation with Repetition
Problem 2.9 Lexicographic Order
Problem 2.10 Set Partition
Problem 2.11 Set Partition 2
Problem 2.12 Bicolor Towers of Hanoi
Problem 2.13 Standard 2´n Table
Problem 2.14 Integer Factorization
[color=FF00FF]Chapter 3 Dynamic Programming[/color]
Problem 3.0 Independent Task Scheduling
Problem 3.1 Coin Changing
Problem 3.2 Relation Ordering
Problem 3.3 Counting Powers
Problem 3.4 Edit Distance
Problem 3.5 Pebble Merging
Problem 3.6 Number Triangles
Problem 3.7 Multiplication Table
Problem 3.8 Renting Boats
Problem 3.9 Car Traveling
Problem 3.10 Minimal m Sums
Problem 3.11 Circle Multiplication
Problem 3.12 Maximum Cube
Problem 3.13 Regular Expressions
Problem 3.14 Bitonic Tours
Problem 3.15 Maximum k Multiplications
Problem 3.16 Cheapest Shopping
Problem 3.17 Collecting Samples
Problem 3.18 Optimal Scheduling
Problem 3.19 String Comparison
Problem 3.20 k Median of Directed Trees
Problem 3.21 k Independent Median of Directed Trees
Problem 3.22 k Median of Directed Line
Problem 3.23 2 Median of Directed Line
Problem 3.24 Maximum Connected Component of Trees
Problem 3.25 k Median of Line
Problem 3.26 k Cover of Line
Problem 3.27 m Processors
Problem 3.28 Red Nodes of Red-Black Trees
[color=FF00FF]Chapter 4 Greedy Algorithms[/color]
Problem 4.1 Lecture Halls
Problem 4.2 Optimal Merge
Problem 4.3 Program Storage
Problem 4.4 Optimal Program Storage
Problem 4.5 Program Storage
Problem 4.6 Optimal Services
Problem 4.7 Optimal Many Services
Problem 4.8 d Forest
Problem 4.9 Oiling Car
Problem 4.10 Interval Cover
Problem 4.11 Coin Changing
Problem 4.12 Delete Numbers
Problem 4.13 Maximum Sequence Differences
Problem 4.14 Nesting Boxes
Problem 4.15 Arbitrage
Problem 4.16 Booster Placement
Problem 4.17 Maximum Tape Utilization Ratio
[/code]
[quote]
[color=FF00FF]
全身心研究数据结构与算法设计中。。。
[/color]
[/quote]
最后更新于：2007-05-09 09:53:00
回复列表 （共110个回复）
11 楼
vcacm [专家分：1500] 发布于 2007-04-29 19:18:00
==========================================================
算法实现题3-11 圈乘运算问题
«问题描述：
关于整数的2 元圈乘运算@;定义为
（X@Y）=10 进制整数X 的各位数字之和*10 进制整数Y 的最大数字+Y 的最小数字。
例如，（9@30）=9*3+0=27。
对于给定的10进制整数X 和K，由X 和@运算可以组成各种不同的表达式。试设计一个
算法，计算出由X 和@;运算组成的值为K 的表达式最少需用多少个 @ 运算。
«编程任务：
给定10 进制整数X 和K (1≤X,K≤10^20) 。编程计算由X 和 # 运算组成的值为K 的表
达式最少需用多少个 @ 运算。
«数据输入：
输入数据由文件名为input.txt的文本文件提供。
每一行有2个10 进制整数X和K。
最后一行是 0 0。
«结果输出:
程序运行结束时，将找到的最少 @ 运算个数输出到文件output.txt中。
输入文件示例 输出示例
input.txt
3 12
0 0
output.txt
1
=========================================================
算法实现题3-12 最大长方体问题
«问题描述：
一个长，宽，高分别为m,n,p 的长方体被分割成个m*n*p 个小立方体。每个小立方体
内有一个整数。试设计一个算法，计算出所给长方体的最大子长方体。子长方体的大小由它
所含所有整数之和确定。
«编程任务：
对于给定的长，宽，高分别为m,n,p 的长方体，编程计算最大子长方体的大小。
«数据输入：
由文件input.txt 提供输入数据。文件的第1 行是3 个正整数m,n,p，1<=m,n,p<=50。接下
来m*n行每行p个正整数，表示小立方体中的数。
«结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是计算
出的最大子长方体的大小。
输入文件示例 输出文件示例
input.txt
3 3 3
0 -1 2
1 2 2
1 1 -2
-2 -1 -1
-3 3 -2
-2 -3 1
-2 3 3
0 1 3
2 1 -3
output.txt
14
==========================================================
算法实现题3-13 正则表达式匹配问题（习题3-22）
«问题描述：
许多操作系统采用正则表达式实现文件匹配功能。一种简单的正则表达式由英文字母、
数字及通配符“*”和“？”组成。“？”代表任意一个字符。“*”则可以代表任意多个字符。
现要用正则表达式对部分文件进行操作。
试设计一个算法，找出一个正则表达式，使其能匹配的待操作文件最多，但不能匹配任
何不进行操作的文件。所找出的正则表达式的长度还应是最短的。
«编程任务：
对于给定的待操作文件，找出一个能匹配最多待操作文件的正则表达式。
«数据输入：
由文件input.txt 提供输入数据。文件由n（1≤n≤250）行组成。每行给出一个文件
名。文件名由英文字母和数字组成。英文字符要区分大小写，文件名长度不超过8个字符。
文件名后是一个空格符和一个字符“+”或“-”。“+”表示要对该行给出的文件进行操作，
“-”表示不进行操作。
«结果输出:
程序运行结束时，将计算出的最多文件匹配数和最优正则表达式输出到文件
output.txt 中。文件的第1 行中的数是计算出的最多文件匹配数。文件的第1 行是最优正
则表达式。
输入文件示例 输出文件示例
input.txt EXCHANGE +
EXTRA +
HARDWARE +
MOUSE -
NETWORK -
output.txt
3
*A*
=========================================================
算法实现题3-14 双调旅行售货员问题
«问题描述：
欧氏旅行售货员问题是对给定的平面上n个点确定一条连接这n个点的长度最短的哈密
顿回路。由于欧氏距离满足三角不等式，所以欧氏旅行售货员问题是一个特殊的具有三角不
等式性质的旅行售货员问题。它仍是一个NP完全问题。最短双调TSP回路是欧氏旅行售货
员问题的特殊情况。平面上n 个点的双调TSP 回路是从最左点开始，严格地由左至右直到
最右点，然后严格地由右至左直至最左点，且连接每一个点恰好一次的一条闭合回路。
«编程任务：
给定平面上n个点，编程计算这n个点的最短双调TSP回路。
«数据输入：
由文件input.txt给出输入数据。第1 行有1 个正整数n，表示给定的平面上的点数。接
下来的n行中，每行2 个实数，分别表示点的x坐标和y坐标。
«结果输出:
将计算的最短双调TSP回路的长度（保留2 位小数）输出到文件output.txt。
输入文件示例 输出文件示例
input.txt 7
0 6
1 0
2 3
5 4
6 1
7 5
8 2
output.txt
25.58
======================================================
算法实现题3-15 最大k乘积问题
«问题描述：
设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的
乘积称为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。
«编程任务：
对于给定的I 和k，编程计算I 的最大k 乘积。
«数据输入：
由文件input.txt提供输入数据。文件的第1 行中有2个正整数n和k。正整数n是序列
的长度；正整数k是分割的段数。
接下来的一行中是一个n位十进制整数。（n<=10）
«结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是计算出
的最大k乘积。
输入文件示例 输出文件示例
input.txt
2 1
15
output.txt
15
==========================================================
12 楼
vcacm [专家分：1500] 发布于 2007-04-29 19:37:00
===================================================
算法实现题3-16 最少费用购物（习题3-20）
«问题描述：
商店中每种商品都有标价。例如，一朵花的价格是2元。一个花瓶的价格是5 元。为了
吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价销
售。例如，3朵花的价格不是6元而是5元。2 个花瓶加1 朵花的优惠价是10 元。试设计一
个算法，计算出某一顾客所购商品应付的最少费用。
«编程任务：
对于给定欲购商品的价格和数量，以及优惠商品价，编程计算所购商品应付的最少费用。
«数据输入：
由文件input.txt提供欲购商品数据。文件的第1行中有1 个整数B（0≤B≤5），表示所
购商品种类数。接下来的B 行，每行有3 个数C，K 和P。C 表示商品的编码（每种商品有
唯一编码），1≤C≤999。K 表示购买该种商品总数，1≤K≤5。P 是该种商品的正常单价（每
件商品的价格），1≤P≤999。请注意，一次最多可购买5*5＝25件商品。
由文件offer.txt提供优惠商品价数据。文件的第1行中有1 个整数S（0≤S≤99），表示
共有S 种优惠商品组合。接下来的S 行，每行的第一个数描述优惠商品组合中商品的种类数
j。接着是j 个数字对（C，K），其中C 是商品编码，1≤C≤999。K 表示该种商品在此组合
中的数量，1≤K≤5。每行最后一个数字P（1≤ P≤9999）表示此商品组合的优惠价。
«结果输出:
程序运行结束时，将计算出的所购商品应付的最少费用输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt
2
7 3 2
8 2 5
offer.txt
2
1 7 3 5
2 7 1 8 2 10
output.txt
14
====================================================
算法实现题3-17 收集样本问题
«问题描述：
机器人Rob在一个有n*n 个方格的方形区域F 中收集样本。（i,j）方格中样本的价值
为v(i,j)，如下图所示。
A
13 6
7
14
21 4
15
14
B
Rob 从方形区域F 的左上角A点出发，向下或向右行走，直到右下角的B 点，在走过的
路上，收集方格中的样本。Rob 从A点到B 点共走2次，试找出Rob 的2条行走路径，使其
取得的样本总价值最大。
«编程任务：
给定方形区域F 中的样本分布，编程计算Rob 的2条行走路径，使其取得的样本总价值最
大。
«数据输入：
由文件input.txt给出输入数据。第1 行有1 个正整数n，表示方形区域F有n*n 个方格。
接下来每行有3 个整数，前2 个表示方格位置，第3个数为该位置样本价值。最后一行是3
个0。
«结果输出:
将计算的最大样本总价值输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
output.txt
67
===========================================================
算法实现题3-18 最优时间表问题
«问题描述：
一台精密仪器的工作时间为n 个时间单位。与仪器工作时间同步进行若干仪器维修程
序。一旦启动维修程序，仪器必须进入维修程序。如果只有一个维修程序启动，则必须进入
该维修程序。如果在同一时刻有多个维修程序，可任选进入其中的一个维修程序。维修程序
必须从头开始，不能从中间插入。一个维修程序从第s个时间单位开始，持续t个时间单位，
则该维修程序在第s+t-1 个时间单位结束。为了提高仪器使用率，希望安排尽可能少的维修
时间。
«编程任务：
对于给定的维修程序时间表，编程计算最优时间表。
«数据输入：
由文件input.txt给出输入数据。第1 行有2 个正整数n和k。n表示仪器的工作时间单
位；k 是维修程序数。接下来的k行中，每行有2 个表示维修程序的整数s和t，该维修程
序从第s个时间单位开始，持续t个时间单位。
«结果输出:
将计算出的最少维修时间输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
15 6
1 2
1 6
4 11
8 5
8 1
11 5
output.txt
11
========================================================
算法实现题3-19 字符串比较问题
«问题描述：
对于长度相同的2 个字符串A和B，其距离定义为相应位置字符距离之和。2 个非空格
字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0；空格与其它字符的距
离为一定值k。
在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干
空格字符所产生的字符串。在字符串A 和B 的所有长度相同的扩展中，有一对距离最小的
扩展，该距离称为字符串A和B的扩展距离。
对于给定的字符串A和B，试设计一个算法，计算其扩展距离。
«编程任务：
对于给定的字符串A和B，编程计算其扩展距离。
«数据输入：
由文件input.txt给出输入数据。第1 行是字符串A；第2 行是字符串B。第3行是空格
与其它字符的距离定值k。
«结果输出:
将计算出的字符串A和B的扩展距离输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
cmc
snmn
2
output.txt
10
======================================================
算法实现题3-20 有向树k中值问题
«问题描述：
给定一棵有向树T，树T 中每个顶点u都有一个权w(u)；树的每条边(u,v)也都有一个
非负边长d(u,v)。有向树T的每个顶点u 可以看作客户，其服务需求量为w(u)。每条边(u,v)
的边长d(u,v) 可以看作运输费用。如果在顶点u 处未设置服务机构，则将顶点u 处的服务
需求沿有向树的边(u,v)转移到顶点v 处服务机构需付出的服务转移费用为w(u)*d(u,v)。
树根处已设置了服务机构，现在要在树T中增设k处服务机构，使得整棵树T 的服务转移费用最小。
«编程任务：
对于给定的有向树T，编程计算在树T中增设k处服务机构的最小服务转移费用。
«数据输入：
由文件input.txt给出输入数据。第1 行有2个正整数n和k。n表示有向树T 的边数；k
是要增设的服务机构数。有向树T 的顶点编号为0，1，…，n。根结点编号为0。接下来的
n行中，每行有表示有向树T的一条有向边的3个整数。第i+1行的3 个整数wi,vi,di分别表
示编号为i 的顶点的权为wi，相应的有向边为(i, vi)，其边长为di。
«结果输出:
将计算的最小服务转移费用输出到文件output.txt。
输入文件示例 输出文件示例
input.txt 4 2
1 0 1
1 1 10
10 2 5
1 2 3
output.txt
4
========================================================
13 楼
bpttc [专家分：8790] 发布于 2007-04-29 19:41:00
似乎都是些ACM的题目
实用算法恐怕不会要求这么高
14 楼
vcacm [专家分：1500] 发布于 2007-04-29 20:06:00
===================================================
算法实现题3-21 有向树独立k中值问题
«问题描述：
给定一棵有向树T，树T 中每个顶点u都有一个权w(u)；树的每条边(u,v)也都有一个
非负边长d(u,v)。有向树T的每个顶点u 可以看作客户，其服务需求量为w(u)。每条边(u,v)
的边长d(u,v) 可以看作运输费用。如果在顶点u 处未设置服务机构，则将顶点u 处的服务
需求沿有向树的边(u,v)转移到顶点v 处服务机构需付出的服务转移费用为w(u)*d(u,v)。
树根处已设置了服务机构，现在要在树T中增设k处独立服务机构，使得整棵树T 的服务转
移费用最小。服务机构的独立性是指任何2 个服务机构之间都不存在有向路经。
«编程任务：
对于给定的有向树T，编程计算在树T中增设k处独立服务机构的最小服务转移费用。
«数据输入：
由文件input.txt给出输入数据。第1 行有2个正整数n和k。n表示有向树T 的边数；k
是要增设的服务机构数。有向树T 的顶点编号为0，1，…，n。根结点编号为0。接下来的
n行中，每行有表示有向树T的一条有向边的3个整数。第i+1行的3 个整数wi,vi,di分别表
示编号为i 的顶点的权为wi，相应的有向边为(i, vi)，其边长为di。
«结果输出:
将计算的最小服务转移费用输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
4 2
1 0 1
1 1 10
10 2 5
1 2 3
output.txt
12
======================================================
算法实现题3-22 有向直线k中值问题
«问题描述：
给定一条有向直线L以及L 上的n+1 个点x0 < x1 <...< xn 。有向直线L 上的每个点xi
都有一个权w(xi) ；每条有向边(xi ,xi_1 ) 也都有一个非负边长d(xi,xi_1) 。有向直线L 上的
每个点xi可以看作客户，其服务需求量为w(xi) 。每条边 (xi ,xi_1 )的边长d(xi,xi_1)可以看
作运输费用。如果在点i x 处未设置服务机构，则将点i x 处的服务需求沿有向边转移到点j x
处服务机构需付出的服务转移费用为w(xi) * d( xi , xj ) 。在点x0 处已设置了服务机构，现在
要在直线L上增设k处服务机构，使得整体服务转移费用最小。
«编程任务：
对于给定的有向直线L，编程计算在直线L 上增设k处服务机构的最小服务转移费用。
«数据输入：
由文件input.txt给出输入数据。第1 行有1个正整数n，表示有向直线L 上除了点0 x 外
还有n 个点n x0 < x1 < ...< x 。接下来的n行中，每行有2个整数。第i+1 行的2个整数分
别表示w(xn_i_1) 和d(xn_i_1,xn_i_2) 。
«结果输出:
将计算的最小服务转移费用输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
9 2
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1
output.txt
26
=======================================================
算法实现题3-23 有向直线2中值问题
«问题描述：
给定一条有向直线L以及L 上的n+1 个点x0 < x1 <...< xn 。有向直线L 上的每个点xi
都有一个权w(xi)；每条有向边 (xi,xi_1)也都有一个非负边长 。有向直线L 上的
每个点xi 可以看作客户，其服务需求量为w(xi)。每条边(xi,xi_1)的边长d(xi,xi_1)可以看作运输费用。如果在点i x 处未设置服务机构，则将点i x 处的服务需求沿有向边转移到点xj处服务机构需付出的服务转移费用为w(xi)* d(xi,xi_1)。在点0 x 处已设置了服务机构，现在要在直线L上增设2处服务机构，使得整体服务转移费用最小。
«编程任务：
对于给定的有向直线L，编程计算在直线L 上增设2处服务机构的最小服务转移费用。
«数据输入：
由文件input.txt给出输入数据。第1 行有1个正整数n，表示有向直线L 上除了点x0外
还有n 个点x0 < x1 <...< xn 。接下来的n行中，每行有2个整数。第i+1 行的2个整数分别表示w(xn_i_1) 和d(xn_i_1,xn_i_1) 。
«结果输出:
将计算的最小服务转移费用输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1
output.txt
26
=====================================================
算法实现题3-24 树的最大连通分支问题
«问题描述：
给定一棵树T，树中每个顶点u 都有一个权w(u)，权可以是负数。现在要找到树T 的一
个连通子图使该子图的权之和最大。
«编程任务：
对于给定的树T，编程计算树T的最大连通分支。
«数据输入：
由文件input.txt给出输入数据。第1 行有1 个正整数n，表示树T 有n 个顶点。树T 的
顶点编号为1，…，n。第2 行有n 个整数，表示n 个顶点的权值。接下来的n-1 行中，每
行有表示树T 的一条边的2 个整数u,v，表示顶点u与顶点v相连。
«结果输出:
将计算出的最大连通分支的权值输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
5
-1 1 3 1 -1
4 1
1 3
1 2
4 5
output.txt
4
=======================================================
算法实现题3-25 直线k中值问题
«问题描述：
在一个按照南北方向划分成规整街区的城市里，n个居民点分布在一条直线上的n个坐
标点x1 <....< xn处。居民们希望在城市中至少选择1 个，但不超过k 个居民点建立服务机构。在每个居民点xi处，服务需求量为wi>=0 ，在该居民点设置服务机构的费用为ci>=0。
假设居民点xi 到距其最近的服务机构的距离为di ，则居民点xi 的服务费用为wi *di 。
建立k 个服务机构的总费用为A+B。A 是在k 个居民点设置服务机构的费用的总和；B
是n个居民点服务费用的总和。
«编程任务：
对于给定直线L 上的n 个点x1 <...< xn ，编程计算在直线L上最多设置k 处服务机构
的最小总费用。
«数据输入：
由文件input.txt给出输入数据。第1 行有2 个正整数n和k。n表示直线L 上有n 个点
x1 <...< xn ；k 是服务机构总数的上限。接下来的n行中，每行有3 个整数。第i+1 行的3个整数xi,wi , ci ，分别表示相应居民点的位置坐标，服务需求量和在该点设置服务机构的
费用。
«结果输出:
将计算的最小服务费用输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
9 3
2 1 2
3 2 1
6 3 3
7 1 1
9 3 2
15 1 6
16 2 1
18 1 2
19 1 1
output.txt
19
==========================================================
15 楼
vcacm [专家分：1500] 发布于 2007-04-29 20:21:00
=====================================================
算法实现题3-26 直线k覆盖问题
«问题描述：
给定一条直线L 上的n 个点x1 << xn，每个点i x 都有一个权w(i) ³ 0，以及在该点
设置服务机构的费用c(i) ³ 0。每个服务机构的覆盖半径为r。直线k 覆盖问题要求找出
{ } n n V x , x , , x = 1 2  的一个子集n S ÍV ， S £ k，在点集S处设置服务机构，使总覆盖费
用达到最小。
直线L 上的每个点i x 是一个客户。每个点i x 到服务机构S的距离定义为
d i S {x y } y S i
= -
Î
( , ) min 。如果客户i x 在S 的服务覆盖范围内，即d(i, S) £ r，则其服务费
用为0，否则其服务费用为w(i)。服务机构S 的总覆盖费用为：
å å
Î =
= +
n
x S j
t S c i w j I j S
i 1
cos ( ) ( ) ( ) * ( , )。
其中I ( j, S)的定义为：
î í ì
>
£
=
d j S r
d j S r
I j S
1 ( , )
0 ( , )
( , ) 。
«编程任务：
对于给定直线L 上的n 个点n x1 << x ，编程计算在直线L上最多设置k 处服务机构
的最小覆盖费用。
«数据输入：
由文件input.txt给出输入数据。第1行有3 个正整数n，k和r。n表示直线L 上有n 个
点n x1 << x ；k 是服务机构总数的上限；r 是服务机构的覆盖半径。接下来的n行中，
每行有3 个整数。第i+1 行的3 个整数xi,wi,ci分别表示i x ,w(i)和c(i)。
«结果输出:
将计算的最小覆盖费用输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
9 3 2
2 1 12
3 2 11
6 3 3
7 1 11
9 3 12
15 1 6
16 2 11
18 1 2
19 1 11
output.txt
19
=================================================
算法实现题3-27 m处理器问题
«问题描述：
在一个网络通信系统中，要将n个数据包依次分配给m 个处理器进行数据处理，并要求
处理器负载尽可能均衡。
设给定的数据包序列为：{ 0 1 1 , , , n- s s  s }。
m 处理器问题要求的是m m r = £ r £ £ r £ n = r 0 1 -1 0  ，将数据包序列划分为m段：
{ 0 1 1 , , r - s  s }，{ 1 2 1 , , r r - s  s }，…，{ 1 , , rm-1 ns
 s }，使 max{( , )}1
1
0 +
-
= i i
m
i
f r r 达到最小。
其中， ( , ) i2 2j f i j = s ++s 是序列{ i j s ,,s }的负载量。
max{( , )}1
1
0 +
-
= i i
m
i
f r r 的最小值称为数据包序列{ 0 1 1 , , , n- s s  s }的均衡负载量。
«编程任务：
对于给定的数据包序列{ 0 1 1 , , , n- s s  s }，编程计算m个处理器的均衡负载量。
«数据输入：
由文件input.txt给出输入数据。第1 行有2 个正整数n和m。n表示数据包个数，m 表
示处理器数。接下来的1 行中有n个整数，表示n个数据包的大小。
«结果输出:
将计算的处理器均衡负载量输出到文件output.txt。保留2 位小数。
输入文件示例 输出文件示例
input.txt
6 3
2 2 12 3 6 11
output.txt
12.32
============================================================
算法实现题3-28 红黑树的红色内结点问题
«问题描述：
红黑树是一类特殊的二叉搜索树，其中每个结点被“染成”红色或黑色。若将二叉搜索
树结点中的空指针看作是指向一个空结点，则称这类空结点为二叉搜索树的前端结点。并规
定所有前端结点的高度为-1。
一棵红黑树是满足下面“红黑性质”染色二叉搜索树：
(1)每个结点被染成红色或黑色；
(2)每个前端结点为黑色结点；
(3)任一红结点的儿子结点均为黑结点；
(4)在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。
从红黑树中任一结点x 出发(不包括结点x)，到达一个前端结点的任意一条路径上的黑
结点个数称为结点x的黑高度，记作bh(x)。红黑树的黑高度定义为其根结点的黑高度。
图示的二叉搜索树是一棵红黑树。标在结点旁边的数字是相应结点的黑高度。
«编程任务：
给定正整数n，试设计一个算法，计算出在所有含有n个结点的红黑树中，红色内结点
个数的最小值和最大值。
«数据输入：
由文件input.txt提供输入数据。文件的第一行是正整数n，1<n<5000。
«结果输出:
程序运行结束时，将红色内结点个数的最小值和最大值输出到文件output.txt 中。第1
行是最小值，第2 行是最大值。
输入文件示例 输出文件示例
input.txt
8
output.txt
1
4
=========================================================
16 楼
vcacm [专家分：1500] 发布于 2007-04-29 20:28:00
第四部分:
[
Chapter 4 Greedy Algorithms
Problem 4.1 Lecture Halls
Problem 4.2 Optimal Merge
Problem 4.3 Program Storage
Problem 4.4 Optimal Program Storage
Problem 4.5 Program Storage
Problem 4.6 Optimal Services
Problem 4.7 Optimal Many Services
Problem 4.8 d Forest
Problem 4.9 Oiling Car
Problem 4.10 Interval Cover
Problem 4.11 Coin Changing
Problem 4.12 Delete Numbers
Problem 4.13 Maximum Sequence Differences
Problem 4.14 Nesting Boxes
Problem 4.15 Arbitrage
Problem 4.16 Booster Placement
Problem 4.17 Maximum Tape Utilization Ratio
Problem 4.18 Task Scheduling
Problem 4.19 N-nary Huffman Codes
Problem 4.20 N-nary Huffman Code Variations
Problem 4.21 Interval Intersections
Problem 4.22 Task Scheduling
Problem 4.23 Optimal Partitions
Problem 4.24 Optimal Partitions with Repetitions
Problem 4.25 Optimal Combinatorial Partitions
Problem 4.26 Planning Traveling
Problem 4.27 Robot Climber
第4章 贪心算法
算法实现题4-1 会场安排问题
算法实现题4-2 最优合并问题
算法实现题4-3 磁带最优存储问题
算法实现题4-4 磁盘文件最优存储问题
算法实现题4-5 程序存储问题
算法实现题4-6 最优服务次序问题
算法实现题4-7 多处最优服务次序问题
算法实现题4-8 d森林问题
算法实现题4-9 汽车加油问题
算法实现题4-10 区间覆盖问题
算法实现题4-11 硬币找钱问题
算法实现题4-12 删数问题
算法实现题4-13 数列极差问题
算法实现题4-14 嵌套箱问题
算法实现题4-15 套汇问题
算法实现题4-16 信号增强装置问题
算法实现题4-17 磁带最大利用率问题
算法实现题4-18 非单位时间任务安排问题
算法实现题4-19 多元Huffman编码问题
算法实现题4-20 多元Huffman编码变形
算法实现题4-21 区间相交问题
算法实现题4-22 任务时间表问题
算法实现题4-23 最优分解问题
算法实现题4-24 可重复最优分解问题
算法实现题4-25 可重复最优组合分解问题
算法实现题4-26 旅行规划问题
算法实现题4-27 登山机器人问题
]
17 楼
vcacm [专家分：1500] 发布于 2007-04-29 20:37:00
===================================================
算法实现题4-1 会场安排问题（习题4-1）
«问题描述：
假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的
贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个
顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小
会场数。)
«编程任务：
对于给定的k个待安排的活动，编程计算使用最少会场的时间表。
«数据输入：
由文件input.txt给出输入数据。第一行有1 个正整数k，表示有k个待安排的活动。接
下来的k行中，每行有2个正整数，分别表示k个待安排的活动开始时间和结束时间。时间
以0 点开始的分钟计。
«结果输出:
将编程计算出的最少会场数输出到文件output.txt。
输入文件示例 输出文件示例
input.txt 5
1 23
12 28
25 35
27 80
36 50
output.txt
3
======================================================
算法实现题4-2 最优合并问题（习题4-5）
«问题描述：
给定k 个排好序的序列s1 , s2 ,... , sk , 用2 路合并算法将这k 个序列合并成一个序列。
假设所采用的2 路合并算法合并2 个长度分别为m和n的序列需要m + n -1次比较。试设
计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。
为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。
«编程任务：
对于给定的k个待合并序列，编程计算最多比较次数和最少比较次数合并方案。
«数据输入：
由文件input.txt给出输入数据。第一行有1 个正整数k，表示有k个待合并序列。接下
来的1 行中，有k个正整数，表示k个待合并序列的长度。
«结果输出:
将编程计算出的最多比较次数和最少比较次数输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
4
5 12 11 2
output.txt
78 52
=======================================================
算法实现题4-3 程序最优存储问题（习题4-6）
«问题描述：
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是i l ，
1 £ i £ n。这n 个程序的读取概率分别是n p , p , , p 2 1  ,且å
=
n
i
i p
1
=1。如果将这n 个程序按
n i ,i , ,i 1 2  的次序存放，则读取程序r i 所需的时间r t =c*å
=
r
k
ik ik p l
1
。这n 个程序的平均读取
时间为å
=
n
r
r t
1
。
磁带最优存储问题要求确定这n 个程序在磁带上的一个存储次序，使平均读取时间达到
最小。试设计一个解此问题的算法,并分析算法的正确性和计算复杂性。
«编程任务：
对于给定的n个程序存放在磁带上的长度和读取概率，编程计算n个程序的最优存储方
案。
«数据输入：
由文件input.txt给出输入数据。第一行是正整数n，表示文件个数。接下来的n行中，
每行有2 个正整数a 和b，分别表示程序存放在磁带上的长度和读取概率。实际上第k个程
序的读取概率å
=
n
i
k i a a
1
/ 。对所有输入均假定c=1。
«结果输出:
将编程计算出的最小平均读取时间输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
5
71 872
46 452
9 265
73 120
35 85
output.txt
85.6193
====================================================
算法实现题4-4 磁盘文件最优存储问题（习题4-7）
«问题描述：
设磁盘上有n 个文件f , f , , fn 1 2  ，每个文件占磁盘上1 个磁道。这n 个文件的检索概
率分别是n p , p , , p 2 1  ,且å
=
n
i
i p
1
=1。磁头从当前磁道移到被检信息磁道所需的时间可用这
2 个磁道之间的径向距离来度量。如果文件i f 存放在第i道上,1 £ i £ n，则检索这n 个文件
的期望时间是å
£i< j£n
i j p p d i j
1
( , )。其中d(i, j)是第i道与第j 道之间的径向距离|i-j|。
磁盘文件的最优存储问题要求确定这n 个文件在磁盘上的存储位置，使期望检索时间达
到最小。试设计一个解此问题的算法，并分析算法的正确性与计算复杂性。
«编程任务：
对于给定的文件检索概率，编程计算磁盘文件的最优存储方案。
«数据输入：
由文件input.txt给出输入数据。第一行是正整数n，表示文件个数。第2 行有n个正整
数ai，表示文件的检索概率。实际上第k个文件的检索概率应为å
=
n
i
k i a a
1
/ 。
«结果输出:
将编程计算出的最小期望检索时间输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
5
33 55 22 11 9
output.txt
0.547396
====================================================
算法实现题4-5 程序存储问题（习题4-8）
«问题描述：
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，
1 <= i <= n。
程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽
可能多的程序。
«编程任务：
对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。
«数据输入：
由文件input.txt给出输入数据。第一行是2 个正整数，分别表示文件个数n和磁带的长
度L。接下来的1 行中，有n个正整数，表示程序存放在磁带上的长度。
«结果输出:
将编程计算出的最多可以存储的程序数输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
6 50
2 3 13 8 80 20
output.txt
5
=========================================================
18 楼
vcacm [专家分：1500] 发布于 2007-04-29 20:49:00
================================================
算法实现题4-6 最优服务次序问题（习题4-11）
«问题描述：
设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1<=i <= n 。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n 个顾客等待服务时间的
总和除以n。
«编程任务：
对于给定的n个顾客需要的服务时间，编程计算最优服务次序。
«数据输入：
由文件input.txt给出输入数据。第一行是正整数n，表示有n 个顾客。接下来的1行中，
有n个正整数，表示n个顾客需要的服务时间。
«结果输出:
将编程计算出的最小平均等待时间输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
10
56 12 1 99 1000 234 33 55 99 812
output.txt
532.00
===================================================
算法实现题4-7 多处最优服务次序问题（习题4-12）
«问题描述：
设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti ,1<= i <= n。共有s 处可以提供此项服务。应如何安排n 个顾客的服务次序才能使平均等待时间达到最小?平均等待时
间是n个顾客等待服务时间的总和除以n。
«编程任务：
对于给定的n个顾客需要的服务时间和s的值，编程计算最优服务次序。
«数据输入：
由文件input.txt 给出输入数据。第一行有2 个正整数n 和s，表示有n 个顾客且有s 处
可以提供顾客需要的服务。接下来的1 行中，有n个正整数，表示n个顾客需要的服务时间。
«结果输出:
将编程计算出的最小平均等待时间输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
10 2
56 12 1 99 1000 234 33 55 99 812
output.txt
336
==================================================
算法实现题4-8 d森林问题（习题4-14）
«问题描述：
设T 是一棵带权树，树的每一条边带一个正权。又设S 是T 的顶点集,T/S 是从树T 中
将S中顶点删去后得到的森林。如果T/S中所有树的从根到叶的路长都不超过d ，则称T/S
是一个d 森林。
(1)设计一个算法求T的最小顶点集S，使T/S是d 森林。(提示：从叶向根移动)
(2)分析算法的正确性和计算复杂性。
(3)设T中有n 个顶点，则算法的计算时间复杂性应为O(n)。
«编程任务：
对于给定的带权树，编程计算最小分离集S。
«数据输入：
由文件input.txt给出输入数据。第一行有1 个正整数n，表示给定的带权树有n个顶点，
编号为1，2，…，n。编号为1 的顶点是树根。接下来的n 行中，第i+1 行描述与i 个顶点
相关联的边的信息。每行的第一个正整数k 表示与该顶点相关联的边数。其后2k 个数中，
每2 个数表示1 条边。第一个数是与该顶点相关联的另一个顶点的编号，第二个数是边权值。
当k=0 时表示相应的结点是叶结点。文件的最后一行是正整数d，表示森林中所有树的从根
到叶的路长都不超过d 。
«结果输出:
将编程计算出的最小分离集S的顶点数输出到文件output.txt。如果无法得到所要求的d
森林则输出“No Solution!”。
输入文件示例 输出文件示例
input.txt
4
2 2 3 3 1
1 4 2
0
0
4
output.txt
1
=====================================================
算法实现题4-10 区间覆盖问题（习题4-17）
«问题描述：
设x1 , x2 ,... , xn 是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?设计解此问题的有效算法，并证明算法的正确性。
«编程任务：
对于给定的实直线上的n个点和闭区间的长度k，编程计算覆盖点集的最少区间数。
«数据输入：
由文件input.txt给出输入数据。第一行有2 个正整数n和k，表示有n个点，且固定长
度闭区间的长度为k。接下来的1 行中，有n个整数，表示n个点在实直线上的坐标（可能相同）。
«结果输出:
将编程计算出的最少区间数输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
7 3
1 2 3 4 5 -2 6
output.txt
3
============================================================
19 楼
vcacm [专家分：1500] 发布于 2007-04-29 21:05:00
=========================================================
算法实现题4-11 硬币找钱问题（习题4-24）
«问题描述：
设有6 种不同面值的硬币，各硬币的面值分别为5 分，1 角，2 角，5 角，1 元，2元。
现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组
Coins［1:6］中，商店里各面值的硬币有足够多。在1 次购物中希望使用最少硬币个数。
例如，1 次购物需要付款0.55 元，没有5 角的硬币，只好用2*20+10+5 共4 枚硬币来
付款。如果付出1 元，找回4 角5 分，同样需要4 枚硬币。但是如果付出1.05 元（1 枚1
元和1 枚5分），找回5 角，只需要3 枚硬币。这个方案用的硬币个数最少。
«编程任务：
对于给定的各种面值的硬币个数和付款金额，编程计算使用硬币个数最少的交易方案。
«数据输入：
由文件input.txt给出输入数据。每一行有6 个整数和1 个有2 位小数的实数。分别表示
可以使用的各种面值的硬币个数和付款金额。文件以6 个0 结束。
«结果输出:
将编程计算出的最少硬币个数输出到文件output.txt。结果应分行输出，每行一个数据。
如果不可能完成交易，则输出”impossible”。
输入文件示例 输出文件示例
input.txt
2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55
0 0 0 0 0 0
output.txt
2
3
====================================================
算法实现题4-12 删数问题（习题4-25）
«问题描述：
给定n 位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个
新的正整数。对于给定的n位正整数a 和正整数k，设计一个算法找出剩下数字组成的新数
最小的删数方案。
«编程任务：
对于给定的正整数a，编程计算删去k个数字后得到的最小数。
«数据输入：
由文件input.txt提供输入数据。文件的第1 行是1 个正整数a。第2 行是正整数k。
«结果输出:
程序运行结束时，将计算出的最小数输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt
178543
4
output.txt
13
=======================================================
算法实现题4-13 数列极差问题（习题4-26）
«问题描述：
在黑板上写了N 个正数组成的一个数列，进行如下操作：每一次擦去其中2 个数设为a
和b，然后在数列中加入一个数a*b+1，如此下去直至黑板上只剩下一个数。在所有按这种操作方式最后得到的数中，最大的数记为max，最小的数记为min，则该数列的极差M 定义
为M = max - min。
«编程任务：
对于给定的数列，编程计算出其极差M。
«数据输入：
由文件input.txt给出输入的数列，第一行是数列的长度N（不超过2000），第二行起是
数列中的N 个数，相邻2 个数由空格分隔。文件名由键盘输入。
«结果输出:
将编程计算出的数列极差M 写入文件output.txt。结果应分两行输出，第一行是数M 的
位数，第二行是数M。
输入文件示例 输出文件示例
input.txt
3
1 1 1
output.txt
1
0
========================================================
算法实现题4-14 嵌套箱问题（习题4-31）
«问题描述：
一个d 维箱(X1,X2,...,Xn)嵌入另一个d 维箱(Y1,Y2,...,Yn)是指存在1,2,…,d 的一个排列π，使得Xπ(1)<Y1 ,Xπ(2) <Y2, ... , Xπ(d)<Yd 。
(1)证明上述箱嵌套关系具有传递性；
(2)试设计一个有效算法，用于确定一个d维箱是否可嵌入另一个d维箱；
(3)给定由n 个d 维箱组成的集合{ B1,B2,B3,...,Bn}，试设计一个有效算法找出这n 个d维箱中的一个最长嵌套箱序列，并用n和d 描述算法的计算时间复杂性。
«编程任务：
给定由n个d维箱，试设计一个有效算法，找出这n个d维箱中的一个最长嵌套箱序列。
«数据输入：
文件input.txt提供输入数据。文件含多个测试项。每个测试数据项的第一行中有2个整
数n 和d，分别表示箱的个数和维数。其后n行每行有d个正整数，表示箱的各维的长度。
«结果输出:
程序运行结束时，对每个测试数据项，输出其最长嵌套箱序列的长度和从小到大排列的
最长嵌套箱序列。所有结果输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt
5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9
output.txt
5
3 1 2 4 5
4
7 2 5 6
=======================================================
算法实现题4-15 套汇问题（习题4-32）
«问题描述：
套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货
币。例如，假定1 美元可以买0.7 英镑，1 英镑可以买9.5 法郎，且1 法郎可以买到0.16美元。通过货币兑换，一个商人可以从1 美元开始买入，得到0.7×9.50.16=1.064美元，从而获得6.4%的利润。
«编程任务：
给定n 种货币c1,c2,c3,...,cn的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。
«数据输入：
由文件input.txt提供输入数据。文件含多个测试数据项。每个测试数据项的第一行中只
有1 个整数n (1<=n<=30)，表示货币总数。其后n行给出n种货币的名称。接下来的一行中
有1 个整数m，表示有m种不同的货币兑换率。其后m行给出m种不同的货币兑换率，每
行有3 个数据项ci ， rij 和cj ，表示货币ci 和cj的兑换率为 rij。文件最后以数字0 结束。
«结果输出:
程序运行结束时，对每个测试数据项j，如果存在套汇的可能性则输出“Case j Yes”， 否则输出“Case j No”。所有结果输出到文件output.txt 中。
输入文件示例 输出文件示例
input.txt
3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0
FrenchFranc
FrenchFranc 0.21 USDollar
0
output.txt
Case 1 Yes
Case 2 No
===========================================================
算法实现题4-16 信号增强装置问题（习题5-20）
«问题描述：
各种资源传输网络的功能是将始发地的资源通过网络传输到一个或多个目的地。例如，
通过石油或者天然气输送管网可以将从油田开采的石油和天然气传送给消费者。 同样，通
过高压传输网络可以将发电厂生产的电力传送给用电消费者。为了使问题更具一般性，用术
语信号统称网络中传输的资源 (石油，天然气，电力等等)。各种资源传输网络统称为信号
传输网络。信号经信号传输网络传输时，需要消耗一定的能量，并导致传输能量的衰减（油
压，气压，电压等等）。当传输能量衰减量（压降）达到某个阈值时，将导致传输故障。为
了保证传输畅通，必需在传输网络的适当位置放置信号增强装置，确保传输能量的衰减量不
超过其衰减量容许值。
为了简化问题，假定给定的信号传输网络是以信号始发地为根的一棵树T。在树T的每
一个结点处（除根结点外）可以放置一个信号增强装置。树T 的结点也代表传输网络的消
费结点。信号经过树T 的结点传输到其儿子结点。树的每一边上的正权是流经该边的信号
所发生的信号衰减量。信号衰减量是可加的。
信号增强装置问题要求对于一个给定的信号传输网络，计算如何放置最少的信号增强装
置来保证网络传输的畅通。
«编程任务：
对于给定的带权树，编程计算放置信号增强装置最少数量。
«数据输入：
由文件input.txt给出输入数据。第一行有1 个正整数n，表示给定的带权树有n个顶点，
编号为1，2，…，n。编号为1 的顶点是树根。接下来的n 行中，第i+1 行描述与i 个顶点
相关联的边的信息。每行的第一个正整数k 表示与该顶点相关联的边数。其后2k 个数中，
每2 个数表示1 条边。第一个数是与该顶点相关联的另一个顶点的编号，第二个数是边权值。
文件的最后一行是正整数d，表示衰减量容许值。
«结果输出:
将编程计算出的最小信号增强装置数输出到文件output.txt。如果无法得到满足要求的
网络则输出“No Solution!”。
输入文件示例 输出文件示例
input.txt
4
2 2 3 3 1
2 1 3 4 2
1 1 1
1 2 2
4
output.txt
1
==================================================
算法实现题4-17 磁带最大利用率问题（习题4-9）
«问题描述：
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1<= i <= n。
程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽
可能多的程序。在保证存储最多程序的前提下还要求磁带的利用率达到最大。
«编程任务：
对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数和占
用磁带的长度。
«数据输入：
由文件input.txt给出输入数据。第一行是2 个正整数，分别表示文件个数n和磁带的长
度L。接下来的1 行中，有n个正整数，表示程序存放在磁带上的长度。
«结果输出:
将编程计算出的最多可以存储的程序数和占用磁带的长度以及存放在磁带上的每个程
序的长度输出到文件output.txt。第1 行输出最多可以存储的程序数和占用磁带的长度；第2
行输出存放在磁带上的每个程序的长度。
输入文件示例 输出文件示例
input.txt
9 50
2 3 13 8 80 20 21 22 23
output.txt
5 49
2 3 13 8 23
======================================================
20 楼
vcacm [专家分：1500] 发布于 2007-04-29 21:17:00
===================================================
算法实现题4-18 非单位时间任务安排问题（习题4-15）
«问题描述：
具有截止时间和误时惩罚的任务安排问题可描述如下。
(1) 给定n个任务的集合S={1,2,…,n}；
(2) 完成任务i 需要ti 时间，1 <= i <= n；
(3) 任务i的截止时间i d ,1≤i≤n，即要求任务i在时间i d 之前结束；
(4) 任务i 的误时惩罚i w ,1≤i≤n,即任务i 未在时间i d 之前结束将招致i w 的惩罚；
若按时完成则无惩罚。
任务安排问题要求确定S 的一个时间表（最优时间表）使得总误时惩罚达到最小。
«编程任务：
对于给定的n个任务，编程计算总误时惩罚最小的最优时间表。
«数据输入：
由文件input.txt给出输入数据。第1行是1 个正整数n，表示任务数。接下来的n行中，
每行有3 个正整数a,b,c，表示完成相应任务需要时间a，截止时间为b，误时惩罚为c。
«结果输出:
将编程计算出的总误时惩罚输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
7
1 4 70
2 2 60
1 4 50
1 3 40
1 1 30
1 4 20
3 6 80
output.txt
110
========================================================
算法实现题4-19 多元Huffman编码问题（习题4-20）
«问题描述：
在一个操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次至少选
2 堆最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，
计算出将n堆石子合并成一堆的最大总费用和最小总费用。
«编程任务：
对于给定n堆石子,编程计算合并成一堆的最大总费用和最小总费用。
«数据输入：
由文件input.txt提供输入数据。文件的第1 行有2 个正整数n和k，表示有n堆石子，
每次至少选2 堆最多选k堆石子合并。第2 行有n个数，分别表示每堆石子的个数。
«结果输出:
程序运行结束时，将计算出的最大总费用和最小总费用输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt
7 3
45 13 12 16 9 5 22
output.txt
593 199
========================================================
算法实现题4-20 多元Huffman编码变形
«问题描述：
在一个操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定在合并过程
中最多可以有m(k)次选k 堆石子合并成新的一堆，2≤k≤n，合并的费用为新的一堆的石子
数。试设计一个算法，计算出将n 堆石子合并成一堆的最小总费用。
«编程任务：
对于给定n堆石子,编程计算合并成一堆的最小总费用。
«数据输入：
由文件input.txt 提供输入数据。文件的第1 行有1 个正整数n，表示有n 堆石子。第2
行有n个数，分别表示每堆石子的个数。第3行有n-1 个数，分别表示m(k)（2≤k≤n）的
值。
«结果输出:
程序运行结束时，将计算出的最小总费用输出到文件output.txt中。问题无解时输出“No
solution!”
输入文件示例 输出文件示例
input.txt
7
45 13 12 16 9 5 22
3 3 0 2 1 0
output.txt
136
========================================================
算法实现题4-21 区间相交问题
«问题描述：
给定x 轴上n 个闭区间。去掉尽可能少的闭区间，使剩下的闭区间都不相交。
«编程任务：
给定n 个闭区间，编程计算去掉的最少闭区间数。
«数据输入：
由文件input.txt给出输入数据。第一行是正整数n，表示闭区间数。接下来的n行中，
每行有2 个整数，分别表示闭区间的2个端点。
«结果输出:
将计算出的去掉的最少闭区间数输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
3
10 20
10 15
20 15
output.txt
2
========================================================
算法实现题4-22 任务时间表问题
«问题描述：
一个单位时间任务是恰好需要一个单位时间完成的任务。给定一个单位时间任务的有限
集S。关于S 的一个时间表用于描述S 中单位时间任务的执行次序。时间表中第1 个任务从
时间0 开始执行直至时间1 结束，第2 个任务从时间1 开始执行至时间2 结束，…，第n个任务从时间n-1 开始执行直至时间n结束。
具有截止时间和误时惩罚的单位时间任务时间表问题可描述如下。
(1) n 个单位时间任务的集合S={1,2,…,n}；
(2) 任务i的截止时间i d ,1≤i≤n,1≤ i d ≤n，即要求任务i 在时间di之前结束；
(3) 任务i 的误时惩罚wi,1≤i≤n,即任务i 未在时间di之前结束将招致wi 的惩罚；
若按时完成则无惩罚。
任务时间表问题要求确定S 的一个时间表（最优时间表）使得总误时惩罚达到最小。
«编程任务：
给定n 个单位时间任务，各任务的截止时间i d ,各任务的误时惩罚i w ,1≤i≤n，编程计算最优时间表。
«数据输入：
由文件input.txt给出输入数据。第一行是正整数n，表示任务数。接下来的2行中，每
行有n个正整数，分别表示各任务的截止时间和误时惩罚。
«结果输出:
将计算出的最小总误时惩罚输出到文件output.txt。
输入文件示例 输出文件示例
input.txt
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
output.txt
50
========================================================
算法实现题4-23 最优分解问题
«问题描述：
设n是一个正整数。现在要求将n分解为若干个互不相同的自然数的和，且使这些自然
数的乘积最大。
«编程任务：
对于给定的正整数n，编程计算最优分解方案。
«数据输入：
由文件input.txt提供输入数据。文件的第1 行是正整数n。
«结果输出:
程序运行结束时，将计算出的最大乘积输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt
10
output.txt
30
=====================================================
算法实现题4-24 可重复最优分解问题
«问题描述：
设n是一个正整数。现在要求将n分解为若干个自然数的和，且使这些自然数的乘积最
大。
«编程任务：
对于给定的正整数n，编程计算最优分解方案。
«数据输入：
由文件input.txt提供输入数据。文件的第1 行是正整数n。
«结果输出:
程序运行结束时，将计算出的最大乘积输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt
10
output.txt
36
=====================================================
算法实现题4-25 可重复最优组合分解问题
«问题描述：
对于任意正整数m，它的取2 组合数定义为{m|2}=m(m-1)/2。设n是一个正整数，
现在要求将n分解为若干个自然数的和，且使这些自然数的取2组合数的乘积最大。
«编程任务：
对于给定的正整数n，编程计算最优分解方案的最大取2 组合数乘积的末尾有多少个0。
«数据输入：
由文件input.txt提供输入数据。文件的第1 行是正整数n。
«结果输出:
程序运行结束时，将计算出的最大取2 组合数乘积的末尾的0 的个数输出到文件
output.txt中。
输入文件示例 输出文件示例
input.txt
5
output.txt
1
=========================================================
我来回复
您所在位置：