题目内容
（请给出正确答案）
问题描述:机器人Rob在一个有n×n个方格的方形区域F中收集样本.(i,j)方格中样本的价值为v(i,j),如图3-6所示.Rob从方形区域F的左上角A点出发,向下或向右行走,
直到右下角的B点,在走过的路上,收集方格中的样本.Rob从A点到B点共走2次,试找出Rob的2条行走路径,使其取得的样本总价值最大.
算法设计:给定方形区域F中的样本分布,计算Rob的2条行走路径,使其取得的样本总价值最大.
数据输入:由文件input.xt给出输入数据.第1行有1个正整数n,表示方形区域F有n×n个方格.按下来每行有3个整数,前2个数表示方格位置,第3个数为该位置样本价值.最后一行是3个0.
结果输出:将计算的最大样本总价值输出到文件output.txt.
如果结果不匹配，请 联系老师 获取答案
更多“问题描述:机器人Rob在一个有n×n个方格的方形区域F中收集…”相关的问题
问题描述:假设有来自n个不同单位的代表参加一次国际会议.铄个单位的代表数分别为ri(i=1,2,...,n).会议餐厅共有m张餐桌,每张餐桌可容纳ci(i=1,2,...,m)个代表就餐.为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐.试设计一个算法,给出满足要求的代表就餐方案.
算法设计:对于给定的代表数和餐桌数以及餐桌容量,计算满足要求的代表就餐方案.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数m和n,m表示餐桌数,n表示单位数(1≤m≤150,1≤n≤270).文件第2行有m个正整数,分别表示每个单位的代表数.文件第3行有n个正整数,分别表示每个餐桌的容量.
结果输出:将代表就餐方案输出到文件output.txt如果问题有解,在文件第1行输出1,否则输出0.接下来的m行给出每个单位代表的就餐桌号.如果有多个满足要求的方案,只要输出一个方案.
算法设计:给定平面上n个点,计算这n个点的最短双调TSP回路.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示给定的平面上的点数.在接下来的n行中,每行2个实数,分别表示点的x坐标和y坐标.
结果输出:将计算的最短双调TSP回路的长度(保留2位小数)输出到文件output.txt.
算法设计:设计一个拉斯维加斯算法,对于给定的自然数n(1≤n≤100)计算在n×n个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格,且放置的皇后互不攻击.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n.
结果输出:将计算的最少皇后数及最佳放置方案输出到文件output.txt.文件的第1行是最少皇后数:接下来的1行是皇后的最佳放置方案.
算法设计:对于给定的维修程序时间表,计算最优时间表.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k.n表示仪器的工作时间单位,k是维修程序数.在接下来的k行中,每行有2个表示维修程序的整数s和t,该维修程序从第s个时间单位开始,持续t个时间单位.
结果输出:将计算出的最短维修时间输出到文件output.txt.
处.居民们希望在城市中至少选择一个,但不超过k个居民点建立服务机构.在每个居民点xi处,服务需求量为wi≥0.在该居民点设置服务机构的费用为ci≥0.假设居民点xi到距其最近的服务机构的距离为di,则居民点x的服务费用为
建立k个服务机构的总费用为A+B.A是在k个居民点设置服务机构的费用的总和;B是n个居民点服务费用的总和.算法设计:对于给定直线上的n个点
,计算在直线L上最多设置k处服务机构的最小总费用.
数据输入:由文件input,txt给出输入数据.第1行有2个正整数n和k.n表示直线L上有n个点k是服务机构总数的上限.接下来的n行中,每行有3个整数.第i+1行的3个整数xi、wi、ci,分别表示相应居民点的位置坐标、服务需求量和在该点设置服务机构的费用.
结果输出:将计算的最小服务费用输出到文件output.txt
圆排列问题描述如下:给定n个大小不等的圆
,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切.圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列.例如,当n=3,且所给的3个圆的半径分别为1、1、2时,这3个圆的最小长度的圆排列见图5-9,其最小长度为
.
算法设计:对于给定的n个圆,计算最小长度圆排列.
数据输入:由文件input.txt提供输入数据.文件的第1行是1个正整数n,表示有n个圆.第2行有n个正数,分别表示n个圆的半径.
结果输出:将计算的最小长度输出到文件output.txt.文件的第1行是最小长度,保留5位小数.
装载问题描述如下:有一批共n个集装箱要装上一艘载重量为c的轮船,其中集装箱i的重量为wi找出一种最优装载方案,将轮船尽可能装满,即在装载体积不受限制的情况下,将尽可能重的集装箱装上轮船.
算法设计:对于给定的n个集装箱和轮船的载重量,计算最优装载方案.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是集装箱数,c是轮船的载重量.接下来的1行中有n个正整数,表示集装箱的重量.
结果输出:将计算的最大装载重量输出到文件output.txt.
规则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每行一个最大总和.
算法设计:对于给定的仓库布局,以及仓库管理员在仓库中的位置和箱子的开始位置和目标位置,设计一个解推箱子问题的分支限界法,计算出仓库管理员将箱子从开始位置推到目标位置所需的最少推动次数.
数据输入:由文件input.txt提供输入数据.输入文件第1行有2个正整数n和m(1≤n,m≤100).表示仓库是n×m个格子的矩形阵列.接下来有n行,每行有m个字符,表示格子的状态.
S——格子上放了不可移动的沉重货物;P——箱子的初始位置;
W——格子空闲:K——箱子的目标位置.
M——仓库管理员的初始位置:
结果输出:将计算的最少推动次数输出到文件output.txt.如果仓库管理员无法将箱子从开始位置推到目标位置则输出“NoSolution!".
算法设计:对于给定的长、宽、高分别为m、np的长方体,计算最大子长方体的大小.
数据输入:文件input.txt提供输入数据,第1行是3个正整数m、n、p(1≤m,n,p≤50).在接下来的m×n行中每行p个正整数,表示小立方体中的数.
结果输出:将计算结果输出到文件output.txt文件的第1行中的数是计算出的最大子长方体的大小.
