问题描述:设某一机器由n个部件组成,每种部件都可以从m个不同的供应商处购得.设wij是从供应商j
算法设计:对于给定的机器部件重量和机器部件价格.设计一个优先队列式分支限界法,计算总价格不超过d的最小重量机器设计.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n、m和d.接下来的2n行,每行n个数.前n行是c,后n行是w.
结果输出:将计算的最小重量,以及每个部件的供应商输出到文件output.txt
算法设计:对于给定的机器部件重量和机器部件价格.设计一个优先队列式分支限界法,计算总价格不超过d的最小重量机器设计.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n、m和d.接下来的2n行,每行n个数.前n行是c,后n行是w.
结果输出:将计算的最小重量,以及每个部件的供应商输出到文件output.txt
第1题
第2题
第5题
工作分配给n个人做的最优和最差分配方案,使产生的总效益最大或最小.
算法设计:对于给定的n件工作和n个人,计算最优分配方案和最差分配方案.
数据输入:由文件input.txt提供输入数据.文件的第1行有1个正整数n,表示有n件工作要分配给n个人做.接下来的n行中,每行有n个整数cij(1≤i≤n,1≤j≤n),表示第i个人做第j件工作产生的效益为cij.
结果输出:将计算的最小总效益和最大总效益输出到文件output.txt.
第6题
架飞机都需要配备在航行技能和语言上能互相配合的2名飞行员,其中名是英国飞行员,另一名是外籍飞行员.在众多的飞行员中,每名外籍飞行员都可以与其他若干名英国飞行员很好地配合.如何选择配对飞行的飞行员才能使一次派出最多的飞机.
算法设计:对于给定的外籍飞行员与英国飞行员的配合情况,找出个最佳飞行员配对方案,使皇家空军一次能派出最多的飞机.
数据输入:由文件input.txt提供输入数据.文件第1行有两个止整数m和n.n是皇家空军的飞行员总数(n<100);m是外籍飞行员数.外籍飞行员编号为1~m;英国飞行员编号为m+1~n.接下来每行有两个正整数i和j,表示外籍飞行员i可以和英国飞行员j配合.文件最后以两个-1结束.
结果输出:将最佳飞行员配对方案输出到文件output.txt.第1行是最佳飞行员配对方案一次能派出的最多的飞机数M.接下来的M行是最佳飞行员配对方案.每行有两个正整数i和j,表示在最佳飞行员配对方案中,飞行员i和飞行员j配对.
如果所求的最佳飞行员配对方案不存在,则输出“NoSolution!".
第8题
补丁程序都有其特定的适用环境,某补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用.一个补丁在排除某些错误的同时,往往会加入另一些错误.换句话说,对于每个补丁i,都有两个与之相应的错误集合B1[j]和B2[i],使得仅当软件包含B1[i]中的所有错误,而不包含B2[i]中的任何错误时,才可以使用补丁i.补丁i将修复软件中的某些错误F1[i],同时加入另一些错误F2[i].另外,每个补丁都耗费一定的时间.
试设计一个算法,利用T公司提供的m个补丁程序,将原软件修复成一个没有错误的软件,并使修复后的软件耗时最少.
算法设计:对于给定的n个错误和m个补丁程序,找到总耗时最少的软件修复方案.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和m,n表示错误总数,m表示补丁总数(1≤n≤20,1≤m≤100).接下来m行给出了m个补丁的信息.每行包括一个正整数,表示运行补丁程序i所需时间以及2个长度为n的字符串,中间用个空格符隔开.在第1个字符串中,如果第k个字符bk为“+”,则表示第k个错误属于B1[i],若为“-”,则表示第k个错误属于B2[i],若为“0”,则第k个错误既不属于B1[i]也不属于B2[i],即软件中是否包含第k个错误并不影响补丁i的可用性.在第2个字符串中,如果第k个字符bk为“+”,则表示第k个错误属于F1[i],若为“-”,则表示第k个错误属于F2[i],若为“0”,则第k个错误既不属于F1[i]也不属于F2[i],即软件中是否包含第k个错误不会因使用补丁i而改变.
结果输出:将总耗时数输出到文件output.txt.如果问题无解,则输出0.
第9题
选取出开区间集合,使得在实直线L的任何一点x,S中包含点x的开区间个数不超过k,且达到最大.这样的集合S被称为开区间集合I的最长k可重区间集.称为最长k可重区间集的长度.
算法设计:对于给定的开区间集合I和正整数k,计算开区间集合I的最长k可重区间集的长度.
数据输入:由文件input.txt提供输入数据.文件的第1行有2个正整数n和k,分别表示开区间的个数和开区间的可重叠数.接下来的n行,每行有2个整数,表示开区间的左、右端点坐标.
结果输出:将计算的最长k可重区间集的长度输出到文件output.txt.
第10题
的m个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径.
规则1:从梯形的顶至底的m条路径互不相交.
规则2:从梯形的顶至底的m条路径仅在数字结点处相交.
规则3:从梯形的顶至底的m条路径允许在数字结点处相交或在边处相交.
算法设计:对于给定的数字梯形,分别按照规则1、规则2和规则3计算出从梯形的顶至底的m条路径,使这m条路径经过的数字总和最大.
数据输入:由文件input,txt提供输入数据.文件的第1行中有2个正整数m和n(m,n≤20),分别表示数字梯形的第1行有m个数字,共有n行.接下来的n行是数字梯形中各行的数字.第1行有m个数字,第2行有m+1个数.....
结果输出:将按照规则1.规则2和规则3计算出的最大数字总和输出到文件output.txt每行一个最大总和.
第11题
量可以使n个仓库的库存数量相同.搬运货物时,只能在相邻仓库之间搬运.
算法设计:对于给定的n个环形排列的仓库的库存量,计算使n个仓库的库存数量相同的最少搬运量.
数据输入:由文件input.txt提供输入数据.文件的第1行中有1个正整数n,表示有n个仓库.第2行中有n个正整数,表示n个仓库的库存量.
结果输出:将计算的最少搬运量输出到文件output.txt.
第12题
动到t.树状路径T.上有若干可移动的障碍物.由于路径狭窄,任何时刻在路径的任何位置不能同时容纳2个物体.每步可以将障碍物或机器人移到相邻的空顶点上.设计一个有效算法用最少移动次数使机器人从s运动到t.
算法设计:对于给定的树T,以及障碍物在树T中的分布情况,计算机器人从起点s到终点t的最少移动次数.
数据输入:由文件input.txt提供输入数据.文件的第1行有3个正整数n,s和t,分别表示树T的顶点数,起点s的编号和终点t的编号.
接下来的n行分别对应于树T中编号为0,1,...,n-1的项点.每行的第1个整数h表示顶点的初始状态,当h+1时表示该顶点为空顶点,当h=0时表示该顶点为满顶点,其中已有一个障碍物.第2个数k表示有k个顶点与该项点相连.接下来的k个数是与该顶点相连的顶点编号.
结果输出:将计算出的机器人最少移动次数输出到文件output.txt.如果无法将机器人从起点s移动到终点t,则输出“NoSolution!"
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!