请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码下载APP
题目内容
（请给出正确答案）
问题描述:子集和问题的一个实例为
.其中,
是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S1,使得
.试设计一个解子集和问题的回溯法.
算法设计:对于给定的正整数的集合
和正整数c,计算S的一个了集S1,使得
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.
结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".
答案
更多“问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否”相关的问题
第1题
和进行这些实验需要使用的全部仪器的集合
.实验Ej需要用到的仪器是I的子集
.配置仪器Ik的费用为ck美元.实验Ej的赞助商已同意为该实验结果支付pj美元.W教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器,才能使太空飞行的净收益最大.这里的净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额.算法设计:对于给定的实验和仪器配置情况,找出净收益最大的实验计划.
数据输入:由文件input.txt提供输入数据.文件第1行有两个正整数m和n,m是实验数,n是仪器数.接下来的m行,每行是一个实验的有关数据.第一个数是赞助商同意支付该实验的费用,然后是该实验需要用到的若干仪器的编号.最后一行的n个数是配置每个仪器的费用.
结果输出:将最佳实验方案输出到文件output.txt.第1行是实验编号,第2行是仪器编号,最后一行是净收益.
第2题
问题描述:给定两个n×n矩阵A和B,试设计一个判定A和B是否互逆的蒙特卡罗算法(算法的计算时间应为O(n2).
算法设计:设计一个蒙特卡罗算法,对于给定的矩阵A和B,判定其是否互逆.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示矩阵A和B为n×n矩阵.接下来的2n行,每行有n个实数,分别表示矩阵A和B中的元素.
结果输出:将计算结果输出到文件output.txt.若矩阵A和B互逆,则输出“YES",否则输出“NO".
第3题
以下哪项最能说明上述广告存在漏洞？
A．上述广告只说明面试中有人撒谎，并未说明测谎器能有效测谎。
B．上述广告未说明为何员工诚实的个人品质，对于一个公司来说至关重要。
C．上述广告忽视了；一个应聘者即使如实地回答了某个问题，仍可能是一个不诚实的人。
D．上述广告依据的只有一个实例，难以论证一般性的结论。
第4题
列出下述问题的真值表，并写出逻辑表达式
①有A、B、C三个输入信号，如果三个输入信号均为0或其中一个为1时，输出信号Y=1，其余情况下，输出Y=0;
②有A、B、C三个输入信号，当三个输入信号出现奇数个1时，输出为1，其余情况下输出为0(这是奇校验的校验位生成器);
③有三个温度探测器，当某个温度探测器的温度超过60℃时，输出信号为1，否则输出信号为0。当有两个或两个以上的温度探测器的输出信号为1时，总控制器输出信号为1，白动控制调控设备使温度降低到60℃以下。试写出总控制器的真值表和逻辑表达式。
第5题
问题描述:关于整数的二元圈乘运算
定义为
(XY)=十进制整数X的各位数字之和x十进制整数Y的最大数字+Y的最小数字
例如,(930)=9*3+0=27.
对于给定的十进制整数X和K,由X和运算可以组成各种不同的表达式.试设计一个算法,计算出由X和运算组成的值为K的表达式最少需用多少个运算.
算法设计:给定十进制整数X和K(1≤X,K≤1020),计算由X和 运算组成的值为K的表达式最少需用多少个运算.
数据输入:输入数据由文件名为input.txt的文本文件提供.每行有2个十进制整数X和K.最后一行是00.
结果输出:将找到的最少运算个数输出到文件output.txt.
第6题
算法设计:设计一个算法,找出给定序列x和y的包含s为其子串的最长公共子序列.
数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x、y和约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.
结果输出:将计算出的x和y的包含s为其子串的最长公共子序列的长度输出到文件output.txt中.
第8题
第9题
第11题
大兵瑞恩被关押在迷宫的东南角,即(N,M)单元里,并已经昏迷.迷宫只有一个入口,在西北角.也就是说,麦克可以直接进入(1,1)单元.另外,麦克从一个单元移动到另一个相邻单元的时间为1,拿取所在单元钥匙的时间及用钥匙开门的时间可忽略不计.
算法设计:试设计一个算法,帮助麦克以最快的方式到达瑞恩所在单元,营救大兵瑞恩.
数据输入:由文件input.txt提供输入数据.第1行有3个整数,分别表示N、M、P的值.第2行是1个整数K,表示迷宫中门和墙的总数.第1+2行(1≤I≤K),有5个整数,依次为Xi1、Yi1、Xi2、Yi2、Gi:
当Gi≥1时,表示(Xi1,Yi1)单元与(Xi2,Yi2)单元之间有一扇第Gi类的门;当Gi=0时,表示(Xi1,Yi1)单元与(Xi2,Yi2)单元之间一堵不可逾越的墙(其中,|Xi1-X2|+Yi1-Yi2|=1,0≤Gi≤P).
第K+3行是一个整数S,表示迷宫中存放的钥匙总数.
第K+3+J行(1≤J≤S)有3个整数,依次为Xi1、Yi1、Qi;表示第J把钥匙存放在(Xi1、Yi1)单元里,并且第J把钥匙是用来开启第Qi类门的(其中1≤Qi≤P).
输入数据中同一行各相邻整数之间用一个空格分隔.
结果输出:将麦克营救到大兵瑞恩的最短时间值输出到文件output.txt.如果问题无解,则输出-1.
