题目
印刷电路板将布线区域划分成n×m个方格阵列(见图6-3(a)).精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案.在布线时,电路只能沿直线或直角布线(见图6-3(b).为了避免线路相交,已布线了的方格做了封锁标记,其他线路不允许穿过被封锁的方格.
算法设计:对于给定的布线区域,计算最短布线方案.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n、m、k,分别表示布线区域方格阵列的行数、列数和封闭的方格数.接下来的k行中,每行2个正整数,表示被封闭的方格所在的行号和列号.最后的2行,每行也有2个正整数,分别表示开始布线的方格(p,q)和结束布线的方格(r,s).
结果输出:将计算的最短布线长度和最短布线方案输出到文件output.txt.文件的第1行是最短布线长度.从第2行起,每行2个正整数,表示布线经过的方格坐标.如果无法布线,则输出“NoSolution!”.
第1题
算法设计:对于给定的n个正整数,设计一个优先队列式分支限界法,用最少的无优先级运算次数产生整数m.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m.第2行是给定的用于运算的n个正整数.
结果输出:将计算的产生整数m的最少无优先级运算次数以及最优无优先级运算表达式输出到文件output.txt.
第3题
算法设计:对于给定的n个元件,改计一个优先队列式分支限界法,计算最佳布线方案,使布线费用达到最小.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n(1≤n≤20).接下来的n-1行,每行n-1个数,表示元件i和元件j之间连线数(1≤i<j≤20).
结果输出:将计算的最小布线费川以及相应的最佳布线方案输出到文件output.txt.
第4题
算法设计:对任意给定的整数n和k,以及完成任务i需要的时间为ti(i=1,2,...,n).设计一个优先队列式分支限界法,计算完成这n个任务的最佳调度.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k.第2行的n个正整数是完成n个任务需要的时间.
结果输出:将计算的完成全部任务的最早时间输出到文件output.txt.
第5题
算法设计:对于给定的机器部件重量和机器部件价格.设计一个优先队列式分支限界法,计算总价格不超过d的最小重量机器设计.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n、m和d.接下来的2n行,每行n个数.前n行是c,后n行是w.
结果输出:将计算的最小重量,以及每个部件的供应商输出到文件output.txt
第8题
装载问题描述如下:有一批共n个集装箱要装上一艘载重量为c的轮船,其中集装箱i的重量为wi找出一种最优装载方案,将轮船尽可能装满,即在装载体积不受限制的情况下,将尽可能重的集装箱装上轮船.
算法设计:对于给定的n个集装箱和轮船的载重量,计算最优装载方案.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是集装箱数,c是轮船的载重量.接下来的1行中有n个正整数,表示集装箱的重量.
结果输出:将计算的最大装载重量输出到文件output.txt.
第9题
0-1背包问题描述如下:给定n种物品和一背包.物品i的重量是wi,其价值为vi,背包的容量为C.问应如何选择装入背包的物品,使得装入背包中物品的总价值最大,在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品i.
0-1背包问题形式化描述如下:给定C>0,wi>0,vi>0(1≤i≤n),要求n元0-1向量,
使得
,而且
达到最大.因此,0-1背包问题是一个特殊的整数规划问题.
算法设计:对于给定的n种物品的重量和价值,以及背包的容量,计算可装入背包的最大价值.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和C,分别表示有n种物品,背包的容量为C.接下来的2行中,每行有n个数、分别表示各物品的价值和重量.
结果输出:将最佳装包方案及其最大价值输出到文件output.txt.文件的第1行是最大价值,第2行是最佳装包方案.
第10题
批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小.
算法设计:对于给定的n个作业,计算最佳作业调度方案.
数据输入:由文件input.txt提供输入数据.文件第1行有1个正整数n,表示作业数.接下来的n行中,每行有2个正整数i和j,分别表示在机器1和机器2上完成该作业所需的处理时间.
结果输出:将最佳作业调度方案及其完成时间和输出到文件output.txt.文件的第1行是完成时间和,第2行是最佳作业调度方案.
为了保护您的账号安全,请在“赏学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!