某人外出旅游,需将n个物品供他选择装入行李袋,但行李袋的重量不能超过w。第i件物品的重量为ai,价值为ci,求这人应装哪几件物品使总重量不超过w,但总价值最大。把这个问题看成多阶段决策问题并利用最优化原理找出递推公式。
A.制成特定形状或形式
B.适合长期使用
C.与所装物品一同报验、一同出售
D.不构成整个物品的基本特征
A.优先选取重量最小的物品
B.优先选取效益最大的物品
C.优先选取单位重量效益最大的物品
D.没有任何准则
A.在工程属性对话框中把“启动对象”设置为Form2
B.在Form1的Load事件过程中加入语句Load Form2
C.在Form2的Load事件过程中加入语句Form2.Show
D.把Fonn2的TabIndex属性设置为1,把Form1的TabIndex属性设置为2
A.你偷了我的钱,理由是你不能证明你没有偷我的钱。
B.有人坚持托勒密的“地心说”,理由是:亚里士多德就是这么认为的。
C.你是有理想的人,所以我也是有理想的人。
D.有人说小李是个品行不端的人,理由是:他的爸爸不是个好东西,爱拈花惹草。
利用贪心法求解0/1背包问题时,(26)能够确保获得最优解。用动态规划方求解O/1背包问题时,将“用前i个物品来装容量是x的背包”的0/1背包问题记为KNAP(1,i,X)设fi(X)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包后取得效益值分别为W和p(j=1~n),则依次求解f0(X),f1(X),…,fn(X)的过程中使用的递推关系式为(27)。
A.优先选取重量最小的物品
B.优先选取效益最大的物品
C.优先选取单位重量效益最大的物品
D.没有任何准则
A.11
B.10
C.9
D.8
从供选择的答案中选出应填入下列叙述中()内的正确答案:
堆是一种有用的数据结构。例如关键码序列(A) 是一个堆。
堆排序是一种(B) 排序,它的一个基本问题是如何建堆,常用的建堆算法是1964年 Floyd提出的(C) 。对含n个元素的序列进行排序时,堆排序的时间复杂性是(D) ,所需的附加存储结点是(E)。
供选择的答案
A:①16,72,31,23,94,53
②94,53,31,72,16,53
③16,53,23,94,31,?2
④16,31,23,94,53,72
⑤94,11,53,23,16,72
B:①插入 ②选择 ③交换 ④基数 ⑤归并
C:①淘汰法 ②筛选法 ③递推法 ④LRU算法
D、E:①O(nlog2n) ②O(n) ③O(log2n)
④O(n2) ⑤O(1)
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)
A.提供某一件事情将会发生的证据来证明一件可替代的事情不会发生。
B.为了证明某人在第一种情况下有一定的责任,在第二种情况下也有相似的责任的声明,揭示了两种情况的相似性。
C.为了支持某人的行动是不负责任的声明,而澄清此人的行动给别人造成的伤害的程度。
D.通过展示一种情况下必不可少的事情与另一种情况下必不可少的事情的不兼容性,证明了两种情况不能同时发生。
以下叙述中,()是正确的。
A.在数据较多、较复杂的情况下使用筛选比使用查询的效果好
B.查询只从一个表中选择数据.而筛选可以从多个表中获取数据
C.通过筛选形成的数据表,可以提供给查询、视图和打印使用
D.查询可将结果保存起来,供下次使用
(34)为计算 a 的值,某人编写了函数 power 如下:
Private Function power (a As Integer, n As Integer) As Long
Dim p As Long
p=a
For k=1 To n
p=p*a
Next k
power=p
End Function
在调试时发现是错误的,例如 Print power(5,4)的输出应该是 625,但实际输出是 3125。程序需要修改。
下面的修改方案中有 3 个是正确的,错误的一个是()。
A)把 For k=1 To n 改为 For k=2 To n
B)把 p=p*a 改为 p=p^n
C)把 For k=1 To n 改为 For k=1 To n-1
D)把 p=a 改为 p=1