请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码下载APP
题目内容
（请给出正确答案）
装载问题描述如下:有一批共n个集装箱要装上一艘载重量为c的轮船,其中集装箱i的重量为wi找出一种最优装载方案,将轮船尽可能装满,即在装载体积不受限制的情况下,将尽可能重的集装箱装上轮船.
算法设计:对于给定的n个集装箱和轮船的载重量,计算最优装载方案.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是集装箱数,c是轮船的载重量.接下来的1行中有n个正整数,表示集装箱的重量.
结果输出:将计算的最大装载重量输出到文件output.txt.
答案
轻松一刻：免费趣味测试
更多“问题描述:试设计一个用队列式分支限界法搜索子集空间树的函数,其参数包括结点可行性判定函数”相关的问题
第3题
.试设计一个优先队列式分支限界法,找出所给n个元件的布线成本最小的布线方案.算法设计:对于给定的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题
.每个作业Ji都有2项任务分别在2台机器上完成.每个作业必须先由机器1处理,再由机器2处理.作业Ji需要机器j的处理时间为tij(=1,2,...,n;j=1,2).对于一个确定的作业调度,设Fij是作业i在机器j上完成处理的时间.所有作业在机器2上完成处理的时间和
称为该作业调度的完成时间和.批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小.
算法设计:对于给定的n个作业,计算最佳作业调度方案.
数据输入:由文件input.txt提供输入数据.文件第1行有1个正整数n,表示作业数.接下来的n行中,每行有2个正整数i和j,分别表示在机器1和机器2上完成该作业所需的处理时间.
结果输出:将最佳作业调度方案及其完成时间和输出到文件output.txt.文件的第1行是完成时间和,第2行是最佳作业调度方案.
第6题
印制电路板将布线区域划分成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!".
第7题
印刷电路板将布线区域划分成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!”.
第9题
问题描述:给定一个无向图G=(V.E),设
是G的顶点集.对任意
,若u∈U且v∈V-U,就称(u,1)为关于顶点集U的条割边.顶点集U的所有割边构成图G的一个割.G的最大割是指G中所含边数最多的割.
算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最大割.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.接下来的m行中,每行有2个正整数u和y,表示图G的一条边(u,v).
结果输出:将计算的最大割的边数和顶点集U输出到文件output.txt.文件的第1行是最大割的边数;第2行是表示顶点集U的向量x(1≤i≤n),x=0表示顶点i不在项点集U中,x=1表示顶点i在顶点集U中.
第10题
问题描述:给定一个赋权无向图G=(V,E),每个顶点
都有权值w(v).如果
,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.
算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).
结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.
