General Search

Description 试设计一个用回溯法搜索一般解空间的函数。该函数的参数包括：生成解空间中下一扩展结点的函数、结点可行性判定函数和上界函数等必要的函数，并将此函数用于解图的m着色问题。 图的m 着色问题描述如下：给定无向连通图G 和m 种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G 中每条边的2 个顶点着不同颜色，则称这个图是m 可着色的。图的m着色问题是对于给定图G和m 种颜色，找出所有不同的着色法。 编程任务： 对于给定的无向连通图G 和m种不同的颜色，编程计算图的所有不同的着色法。 Input 输入由多组测试数据组成。 每组测试数据输入的第一行有3 个正整数n，k 和m，表示给定的图G 有n个顶点和k条边，m种颜色。顶点编号为1，2，…，n。接下来的k行中，每行有2个正整数u,v，表示图G 的一条边(u,v)。 Output 对应每组输入，输出的每行是计算出的不同的着色方案数。 Sample Input 5 8 4 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5 Sample Output 48

排列树问题 对于给定的n个圆，编程计算最小长度排列。

Description 试设计一个用回溯法搜索排列空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解圆排列问题。 圆排列问题描述如下：给定n 个大小不等的圆c1 , c2 ,..., cn ，现要将这n 个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n 个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3 个圆的半径分别为1，1，2 时，这3 个圆的最小长度的圆排列是1,2,1，其最小长度为2 + 4*sqr(2)。 编程任务： 对于给定的n个圆，编程计算最小长度排列。 Input 输入由多组测试数据组成。 每组测试数据输入的第一行是1 个正整数n，表示有n个圆。第2行有n个正数，分别表示n个圆的半径。 Output 对应每组输入，输出的每行是计算出的最小长度，保留3 位小数。 Sample Input 3 1 1 2 Sample Output 7.657

0-1 Knapsack 试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解0-1背包问题。

Description 试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解0-1背包问题。 0-1 背包问题描述如下：给定n 种物品和一个背包。物品i的重量是wi，其价值为vi ，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2 种选择，即装入背包或不装入背包。不能将物品i 装入背包多次，也不能只装入部分的物品i。 Input 输入由多组测试数据组成。 每组测试数据输入的第一行有2个正整数n和c。n是物品数，c是背包的容量。接下来的1 行中有n个正整数，表示物品的价值。第3 行中有n个正整数，表示物品的重量。 Output 对应每组输入，输出的2行是装入背包物品的最大价值和最优装入方案。 Sample Input 5 10 6 3 5 4 6 2 2 6 5 4 Sample Output 15 1 1 0 0 1

子集树问题 试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解装载问题。

Description 试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解装载问题。 装载问题描述如下：有一批共n个集装箱要装上艘载重量为c的轮船，其中集装箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。 Input 输入由多组测试数据组成。 每组测试数据输入的第一行有2个正整数n和c，n是集装箱数，c是轮船的载重量。接下来的1行中有n个正整数，表示集装箱的重量。 Output 对应每组输入，输出的每行是将计算出的最大装载重量。 Sample Input 5 10 7 2 6 5 4 Sample Output 10

汽车加油问题 对于给定的n和k个加油站位置，编程计算最少加油次数。

Description 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。 编程任务： 对于给定的n和k个加油站位置，编程计算最少加油次数。 Input 输入由多组测试数据组成。 每组测试数据输入的第一行有2 个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。 Output 对应每组输入，输出的每行是计算出的最少加油次数。如果无法到达目的地，则输出”No Solution”。 Sample Input 7 7 1 2 3 4 5 1 6 6 Sample Output 4

程序存储问题 对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。

Description 设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是li ，1 ≤ i ≤ n。程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。 编程任务： 对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。 Input 输入由多组测试数据组成。 每组测试数据输入的第一行是2 个正整数，分别表示文件个数n和磁带的长度L。接下来的1 行中，有n个正整数，表示程序存放在磁带上的长度。 Output 对应每组输入，每行输出的是计算出的最多可以存储的程序数。 Sample Input 6 50 2 3 13 8 80 20 Sample Output 5

Optimal Services

Description 设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti ，1 ≤ i ≤ n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n 个顾客等待服务时间的总和除以n。 编程任务： 对于给定的n个顾客需要的服务时间，编程计算最优服务次序。 Input 输入由多组测试数据组成。 每组测试数据输入的第一行是正整数n，表示有n 个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。 Output 对应每组输入，输出的每行是计算出的最小平均等待时间。 Sample Input 10 56 12 1 99 1000 234 33 55 99 812 Sample Output 532.00

数据结构课程设计大作业 分油问题

有三个大小不等的、没有刻度的油桶，分别能装x、y、z公斤油。开始时，第一个油桶装满油，另外两个油桶为空，要求找出一种步骤最少的分油方法，在某一个油桶上分出targ公斤油。 输入：三个油桶的装油量（例如分别为80、50、30公斤）和需要分出的油量targ公斤（例如为40公斤）；

背包问题 贪心算法

Description 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。 编程任务： 对于给定的n种物品和一个背包容量C，编程计算装入背包中最大的物品总价值。 Input 输入由多组测试数据组成。 每组测试数据输入的第1行中有2个正整数n和C。正整数n是物品个数；正整数C是背包的容量。接下来的2行中，第一行有n个正整数，分别表示n个物品的重量，它们之间用空格分隔；第二行有n个正整数，分别表示n个物品的价值，它们之间用空格分隔。 Output 对应每组输入，输出的每行是计算出的装入背包中最大的物品总价值，保留一位有效数字。 Sample Input 3 50 10 20 30 60 100 120 Sample Output 240.0

Lecture Halls 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。)

Problem D:Lecture Halls Description 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。) 编程任务： 对于给定的k个待安排的活动，编程计算使用最少会场的时间表。 Input 输入数据是由多组测试数据组成。每组测试数据输入的第一行有1 个正整数k，表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。 Output 对应每组输入，输出的每行是计算出的最少会场数。 Sample Input 5 1 23 12 28 25 35 27 80 36 50 Sample Output 3