关于0-1背包问题的下述形式化公式描述:下述说法不正确的是()。
A.i表示物品的重量
B.C表示背包容量
C.xi=0表示编号为i的物品不被选择
D.求解目标是最大化装入背包内的物品的总价值
A.i表示物品的重量
B.C表示背包容量
C.xi=0表示编号为i的物品不被选择
D.求解目标是最大化装入背包内的物品的总价值
0-1背包问题可以描述为:有n个物品,对i=1,2,…,n,第i个物品价值为vi ,重量为wi(vi,和wi为非负数),背包容量为W(W为非负数),选择其中一些物品装入背包,使装入背包物品的总价值最大,,且总重量不超过背包容量,即,其中,xi∈{0,1},xi=0表示第i个物品不放入背包,xi=1表示第i个物品 放入背包。
【问题1】(8分)
用回溯法求解此0-1背包问题,请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点己经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v,w,k,W)函数,其中v, w, k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。
下面给出0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。
变量说明如下:
cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。
BKNAP(W,n,w,v,fw,fp,X)
1 cw ← cp ← 0
2 (1)
3 fp ← -1
4 while true
5 while k≤n and cw+w[k]≤W do
6 (2)
7 cp ← cp+v[k]
8 Y[k]← 1
9 k ← k+1
10 if k>n then
11 if fp<cp then
12 fp ← cp
13 fw ← ew
14 k ← n
15 X ← Y
16 else Y(k)← 0
17 while BOUND(cp,cw,k,W) ≤fp do
18 while k≠0 and Y(k)≠1 do
19 (3)
20 if k=0 then return
21 Y[k]←0
22 cw ← cw ← w[k]
23 cp ← cp ← v[k]
24 (4)
【问题 1】(8 分)
用回溯法求解此 0-1 背包问题,请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v,w,k,W )函数,其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。
下面给出 0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。
变量说明如下:
cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。
以下关于网络安全漏洞的描述中,哪项是错误的?——
A.网络服务是通过各种协议来完成的
B.形式化证明的方法可有效防范黑客攻击
C.网络协议的漏洞是Intemet面临的一个严重安全问题
D.我们常用的’relnet、FFP、HTFP协议,在安全方面都存在一定的问题
以下关于软件开发方法的叙述,错误的是()。
A.对于较为复杂的应用问题,适合采用形式化方法进行需求分析 B.形式化方法的优势在于能够精确地表述和研究应用问题及其软件实现 C.净室软件工程将正确性验证作为发现和排除错误的主要机制 D.净室软件工程强调统计质量控制技术,包括对客户软件使用预期的测试
以下关于对象、类和继承的叙述中,不正确的是()
A.对象是系统中用来描述客观事务的一个模块,是构成系统的基本单位
B.类是现实世界中实体的形式化描述
C.对象是类的实例,类是对象的模板
D.继承表示对象之间的层次关系
以实数集为个体城,用谓词公式将下列语句形式化
(1)如果两实数的平方和为零;那么这两个实数均为零,
(2)F(x)为一实函数当且仅当对每一实数元都有且只有一个实数y满足y=f(x)(不得使用量词为实函数:可译为
简述你参加过软件应用开发项目的概要和你所担任的工作,包括你选用软件架构的经验。