首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 0-1背包问题定义为:给定i个物品的价值v[1…i]、重量w[1…i]和背包容量T,每个物品装到背包里或者不装到背包里。求最优的装包方案,使得所得到的价值最大。
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 0-1背包问题定义为:给定i个物品的价值v[1…i]、重量w[1…i]和背包容量T,每个物品装到背包里或者不装到背包里。求最优的装包方案,使得所得到的价值最大。
admin
2021-03-24
109
问题
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
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程序
#include<Stdio.h>
#include<math.h>
#define N 6
#define maxT 1000
int c[N][maxT]={0};
intMemoized_Knapsack(int V[N],int w[N],intT){
inti;
int j;
for(i=0;i<N;i++){
for(j=0;j<=T;j++){
c
[j]=一1;
}
}
returnCalculate_Max_Value(v,w,N-1,T);
}
intcalculate_Max_Value(int v[N], int w[N],inti,int j){
int temp=0;
if(c
[j]!=一1){
return
(1)
;
}
if(i=0 || j==0){
c
[j]=0;
}else{
c
[j]=Calculate_Max_Value(v,w,i-1,j);
if(
(2)
){
temp=
(3)
;
if(c
[j]<temp){
(4)
;
}
}
}
return c
[j];
}
根据说明和C代码,填充C代码中的空(1)~(4)。
选项
答案
(1)c[i][j] (2)w[i]<=j (3)Calculate_Max_Value(v,w,i-1 j-w[i])+v[i] (4)c[i][j]=temp
解析
一般情况下,采用动态规划法求解最优化问题是构建递归式,然后自底向上迭代地求解。这里采用了自顶向下的递归求解方法,但是和传统的递归又不同。在求解问题的过程中,对第一次遇到的问题采用递归方法求解,把解存放到数组中,后面再次遇到该问题时,直接到数组中查询。
C程序中已经说明c
[j]表示前i个物品在背包容量为j的情况下最优装包方案所能获得的最大价值。开始时c
[j]初始化为一1。calculate_Max_Value函数用来计算c
[j]的值。进入函数后,先判断c
的值是否为-1,如果不是,说明己经计算过,直接返回该值即可,因此空(1)填c
[j];如果是-1,那么需要递归计算。空(2)上面的语句计算了在前i-1项,容量为j的背包问题值的最大价值,因此空(2)填入w
<=j,考虑在前i-1项,容量为j-w
的背包问题值的最大价值,比较两者的大小关系,因此空(3)和空(4)分别填入Calculate_Max_Value(v,w,i-1 j-w
)+v
和c
D]=temp。
转载请注明原文地址:https://kaotiyun.com/show/LoxZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
请分别说出(1)与(2)的设备名称。目前常见宽带接入的方式有哪几种?
阅读以下说明,回答问题1~3,将解答填入对应的解答栏内。某公司的分支机构通过一条DDN专线接入到公司总部,地址分配和拓扑结构如图5-1所示。在两台路由器之间可以使用静态路由,也可以使用动态路由。在[问题1]和[问题2]中,所使用的是静态路
文件/etc/sysconfig/network-scripts/eth0用于存储网络配置信息,请根据图2-1填写下面的空缺信息,完成主机的配置。DEVICE=eth0HWADDR=(7)ONBOOT=yesBOOT
阅读以下说明,回答问题1至问题5,将解答填入对应的解答栏内。[说明]某网络拓扑结构如图3-1所示,网络1和网络2的主机均由DHCP_Server分配IP地址。FTPServer的操作系统为WindowsServer2003,Web_S
SDLCwasinventedbyIBMtoreplacetheolderBisynchronousprotocolforwideareaconnectionsbetweenIBMequipment.Avarietio
FrameRelayissimplifiedformof(66),similarinprincipleto(67),inwhichsynchronous,framesofdataareroutedtodifferent
FrameRelayissimplifiedformof(66),similarinprincipleto(67),inwhichsynchronous,framesofdataareroutedtodifferent
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjust
Routingprotocolsusedifferenttechniquesforassigning(1)toindividualnetwork.Further,eachroutingprotocolformsametricag
栈是一种按“后进先出”原则进行插入和删除操作的数据结构,因此,__________必须用栈。(2010年上半年试题)
随机试题
44岁女性,肝脏进行性肿大,疼痛明显,移动性浊音(+),肝肋下6.0cm,脾肋下1.5cm,对症治疗效果不佳,腹围增加明显,出现阵发性低血糖,最可能诊断
“至虚有盛候”,其疾病的本质属
关于产程图,下列哪项说法正确
A.开闭口运动B.前后运动C.侧方运动D.边缘运动E.咀嚼运动哪一项是指下颌向各个方向所作最大范围的运动
李女士在单位集体体检中发现左侧乳房有肿块来院治疗,后经医师诊断后拟手术切除左侧乳房治疗。但患者十分担心术后会影响今后的生活质量,医师积极解释后,病人的心理负担消除。在征得患者家属同意的情况下,进行手术且手术顺利,患者及家属都很满意。本案例集中体现了应尊重患
我们常在大楼里面见到消火栓箱,里面放置的有消防器材等灭火设施,消火栓箱的完整与否关系到整栋大楼的消防安全。下列符合消火栓箱检查验收规定的是()
外资股只有发行行为要受到境外募集行为发生地有关法律的约束。()
下列属于一国国际储备资产的有()。
Whatdoesthehamburgersayaboutourmodernfoodeconomy?Alot,actually.OverthepastseveralyearsWaldoJaquithintendedt
Animportantpartofpolicestrategy,rapidpoliceresponseisseenbypoliceofficersandthepublicalikeasofferingtremendo
最新回复
(
0
)