题目内容
（请给出正确答案）
如果结果不匹配，请 联系老师 获取答案
更多“考虑最大团问题的子集空间树中第i层的一个结点x,设MinDe…”相关的问题
0-1背包问题描述如下;给定n种物品和一个背包.物品i的重量是wi,其价值为vi背包的容量为C.应如何选择装入背包的物品,使装入背包中物品的总价值最大？
在选择装入肯包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品i.
0-1背包问题形式化描述如下:给定
,要求n元0-1向量
,
使得
而且
达到最大.
算法设计:对于给定的n种物品的重量和价值,以及背包的容量,计算可装入背包的最大价值.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是物品数,c是背包的容量.接下来的1行中有n个正整数,表示物品的价值.第3行中有n个正整数,表示物品的重量.
结果输出:将计算的装入背包物品的最大价值和最优装入方案输出到文件output.txt
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行是最佳装包方案.
.每个作业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行是最佳作业调度方案.
问题描述:子集和问题的一个实例为
.其中,
是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得
.试设计一个解子集和问题的回溯法.
算法设计:对于给定的正整数的集合
和正整数c,计算S的一个了集S1,使得
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.
结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".
范围查询的另一解法需要借助范围树(range tree)。
为此，首先仿照如图8.37(教材240页)和图8.38(教材241页)所示的策略，按x坐标将平面上所有输入点组织为一棵平衡二叉搜索树，称作主树(main tree)。
于是如图x8.10(a)和(b)所示，该树中每个节点各自对应于一个竖直的条带区域;左、右孩子所对应的条带互不重叠，均由父节点所对应的条带垂直平分而得;同一深度上所有节点所对应的条带也互不重叠，而且它们合并后恰好覆盖整个平面。
接下来，分别对于主树中每一节点，将落在其所对应条带区域中的输入点视作一个输入子集，并同样采用以上方法，按照y坐标将各个子集组织为一棵平衡二叉搜索树，它们称作关联树(associative tree)。于是如图x8.10(a)和(c)所示，每棵关联树所对应的竖直条带，都会进而逐层细分为多个矩形区域，且这些矩形区域也同样具有以上所列主树中各节点所对应条带区域的性质，至此，主树与这o(n)棵关联树构成了一个两层的嵌套结构，即所谓的范围树。
利用范围树，可按如下思路实现高效的范围查询，对于任一查询范围R=[x1，x2]×[y1，y2]，首先按照[x1，x2]对主树做一次×方向的范围查询。根据8.4.1节的分析结论，如此可以得到o(logn)个节点，而且如x8.10(b)所示，它们所对应的竖直条带互不重叠，它们合并后恰好覆盖了x坐标落在[x1，x2]范围内的所有输入点。
接下来，深入这些节点各自对应的关联树，分别按照[y1，y2]做一次y方向的范围查询。如此从每棵关联树中取出的一系列节点，也具有与以上取自主树的节点的类似性质，具体地如图x8.10(c)所示，这些节点所对应的矩形区域互不重叠，且它们合并之后恰好覆盖了当前竖直条带内y坐标落在[y1，y2]范围内的所有输入点。换而言之，这些点合并之后将给出落在R中的所有点，既无重也不漏。
a)试证明，如此实现的范围树，空间复杂度为o(nlogn);
b)按照以上描述，试利用你的范围树实现新的范围查询算法;
c)试证明，以上范围查询算法的时间复杂度为O(r+log2n)，其中r为实际命中并被报告的点数;
d)继续改进以上范围树，在不增加空间复杂度的前提下，将查询时间减至O(r+logn)。
利用401KSUBS.RAW中size=1的一个子集; 这就将分析仅限于单身者。(见计算机习题第4章第8题。)
(i)样本中最年轻的人多少岁？这个年龄的有多少人？
(ii)在模型中，β2的字面解释是什么？它本身有什么意义吗？
(iii)估计第(ii)部分中的模型，并以标准形式报告结果。你关心age的系数为负吗？请解释。
(iv)由于样本中最年轻者为25岁，若认为给定收入水平下，25岁时净总金融资产的平均量最低，这有意义吗？记得age对nettfa的偏效应为β2+2β3age，所以在25岁时的偏效应为β2+2β2(25)=β2+50β3称之为θ2。求并得到检验H0：θ2=0的双侧P值。你应该得到θ2很小且在统计上也不显著的结论。
考虑一家公司在今后5个时期内确定劳动力多少的问题。如果在5个时期中所需劳动力的最低数bi(i=1，2，3，4和5)是5、7、8、4和6。设yi(≥bi)是第i个时期所拥有的实际劳动力。如果yi超过bi，那么发生多余成本
c1(yi-bi)=3(yi-bi)c1(yi-bi)=3(yi-bi)
如果yi-1小于yi，那么发生雇用成本
把这个问题表示成一个动态规划模型并求出最优解，如果开始时雇佣的人员是y0=5的话。如果y0=3，对解有什么影响？
圆排列问题描述如下:给定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位小数.
