假定要把长为的n个程序放在磁带T1和T2上,并且希望按照使最大检索时间取最小值的方式存
假定要把长为的n个程序放在磁带T1和T2上,并且希望按照使最大检索时间取最小值的方式存放,即如果存放在T1和T2上的程序集合分别是A和B,则希中所选择的A和B使得取最小值.
贪心算法:开始将A和B都初始化为空,然后一次考虑一个程序.如果则将当前正在考虑的那个程序分配给A,否则分配给B.证明无论是按还是按的次序来考虑程序的,这种方法都不能产生最优解.应当采用什么策略?写出一个完整的算法并证明其正确性.
假定要把长为的n个程序放在磁带T1和T2上,并且希望按照使最大检索时间取最小值的方式存放,即如果存放在T1和T2上的程序集合分别是A和B,则希中所选择的A和B使得取最小值.
贪心算法:开始将A和B都初始化为空,然后一次考虑一个程序.如果则将当前正在考虑的那个程序分配给A,否则分配给B.证明无论是按还是按的次序来考虑程序的,这种方法都不能产生最优解.应当采用什么策略?写出一个完整的算法并证明其正确性.
(1)试给出i和j的取值范围;
(2)试给出通过i和j求解k的公式.
(1)α1=(1,-2,5)T,α2=(3,2,-1)T,α3=(3,10,-17)T;
(2)α1=(1,3,5,-1)T,α2=(2,-1,-3,4)T,α3=(5,1,-1,7)T,α4=(7,7,9,1)T。
算法设计:对于给定的长、宽、高分别为m、np的长方体,计算最大子长方体的大小.
数据输入:文件input.txt提供输入数据,第1行是3个正整数m、n、p(1≤m,n,p≤50).在接下来的m×n行中每行p个正整数,表示小立方体中的数.
结果输出:将计算结果输出到文件output.txt文件的第1行中的数是计算出的最大子长方体的大小.
算法设计:对于给定的仓库布局,以及仓库管理员在仓库中的位置和箱子的开始位置和目标位置,设计一个解推箱子问题的分支限界法,计算出仓库管理员将箱子从开始位置推到目标位置所需的最少推动次数.
数据输入:由文件input.txt提供输入数据.输入文件第1行有2个正整数n和m(1≤n,m≤100).表示仓库是n×m个格子的矩形阵列.接下来有n行,每行有m个字符,表示格子的状态.
S——格子上放了不可移动的沉重货物;P——箱子的初始位置;
W——格子空闲:K——箱子的目标位置.
M——仓库管理员的初始位置:
结果输出:将计算的最少推动次数输出到文件output.txt.如果仓库管理员无法将箱子从开始位置推到目标位置则输出“NoSolution!".
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!