首页
登录
从业资格
0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1…i]和背包容
0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1…i]和背包容
练习题库
2022-08-02
75
问题
0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1…i]和背包容量T,每个物品装到背包里或者不装到背包里。求最优的装包方案,使得所得到的价值最大。0-1背包问题具有最优子结构性质。定义c
[T]为最优装包方案所获得的最大价值,则可得到如下所示的递归式。
【c代码】下面是算法的C语言实现。(1)常量和变量说明T:背包容量v[]:价值数组w[]:重量数组c[][]:c
[j]表示前i个物品在背包容量为j的情况下最优装包方案所能获得的最大价值(2)C程序
【问题1】(8分)根据说明和C代码,填充C代码中的空(1)-(4)。【问题2】(4分)根据说明和C代码,算法采用了(5)设计策略。在求解过程中,采用了(6)(自底向上或者自顶向下)的方式。【问题3】(3分)若5项物品的价值数组和重量数组分别为v[]={0,1,6,18,22,28}和w[]={0,1,2,5,6,7}背包容量为T=11,则获得的最大价值为(7)。
选项
答案
解析
【问题1】
(1)c
[j]
(2)i>0&&j>=w
(3)Calculate_Max_Value(v,w,i-1,j-w
)+v
(4)c
[j]=temp
【问题2】
(5)动态规划
(6)自顶向下
【问题3】
(7)40
本题考查的是动态规划法,将中间结果存在二维数组c[][]当中。
【问题1】
结合题干描述中的递归式,函数最终返回值应该是c
[T],又根据代码上下文,T在函数中传参为j,所以第(1)空返回的结果为c
[j]。
根据递归式和代码上下文可知,c
[j]=0已处理,if后面处理的是max递归部分,又根据上下文可以看到temp会与c
[j]进行比较,递归时i=i-1,所以这里判断的是temp与c[i-1][T]的值,第(3)空的处理是将c[i-1][j-w
]+v
传递给temp,即temp=Calculate_Max_Value(v,w,i-1,j-w
)+v
,注意这里不是直接穿c[][]数组值,而是递归调用Calculate_Max_Value()函数。那么第(2)空缺失的判断条件根据第3个表达式条件为i>0且T>=w
,对应代码中的参数即i>0&&j>=w
。
第(4)空是c
[j]<temp比较后的返回值,根据题干,我们需要返回max最大值,最终返回的结果是c
[j],因此要保证c
[j]最大,当c
[j]<temp时,将temp赋值给c
[j],即c
[j]=temp。
【问题2】
本题采用递归形式,并且求取的是全局最优解,中间结果存在二维数组c[][]当中,所以采用的是动态规划法。动态规划法采用递归形式,i会从N-1递减至0,所以是自顶向下的方式。
【问题3】
本题考查最优解,可以忽略题干描述,直接凑数,可得第3和第4个物品,重量为11,价值为40,此时为最优解,即为最大价值。
转载请注明原文地址:https://tihaiku.com/congyezige/2409598.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
在设计分E-R图阶段,人力部门定义的员工实体具有属件:员工号,姓名,性别和出生日
在设计分E-R图阶段,人力部门定义的员工实体具有属件:员工号,姓名,性别和出生日
一级封锁协议解决了事务的并发操作带来的_()_不一致性的问题。A.数据丢失修改
将具有特定功能的一段SQL语句(多于一条)在数据库服务器上进行预先定义并编译,
以下对存储过程的叙述中,不正确的是()A.存储过程可以定义变量 B.存储过程
在文件系统阶段的信息处理中,人们关注的中心问题是系统功能的设计,因而处于主导地位
下列叙述中正确的是()。A.算法的效率只与问题规模有关,与存储结构无关 B.
算法的时间复杂度取决于()。 A.问题的规模 B.问题的困难度 C.待处
一级封锁协议解决了事务的并发操作带来的_()_不一致性的问题。A.数据丢失修改
下表中两个事务的调度带来的问题是() A.丢失修改 B.读脏数据 C.没
随机试题
ManyfamiliesintheUnitedStateshavealargerincomenowthaneverbefore
Itisacommonplaceamongmoraliststhatyoucannotgethappinessbypursuin
桥梁盆式支座试验,要求卸载后残余变形不得超过支座设计荷载下相应变形的3%。
呼吸过缓见于A.镇静剂过量 B.胸膜炎 C.腹水 D.发热 E.贫血
根据《全国中小企业股份转让系统挂牌业务问答一关于挂牌条件适用若干问题的解答(一)
下列关于效力未定的民事法律行为的说法中,错误的是:A.效力未定的民事法律行为经权
女性,49岁,胸部外伤致开放性气胸,出现呼吸抑制和发绀,立即封闭胸壁伤口,行闭式
关于ETF申购、赎回的表述,正确的有()。A:基金管理人有权对ETF的最小申购、
教育从生产劳动中第一次分离的标志是()。 A.国家的出现B.阶级的分化
A.产生毒副作用 B.减轻毒副作用 C.发生拮抗作用 D.抑制药物活性
最新回复
(
0
)