首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
69
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
请简要说出DHCP服务的基础流程?请分别写出查看客户机TCP/IP的详细配置信息、手工释放IP地址、重新向DHCP服务器申请IP地址Windows2000命令。
认真阅读以下基于Windows2003操作系统IPv6的技术说明,根据要求回答问题1至问题4。【说明】由于现有的网络设备大部分都是基于IPv4的,也不可能在短时间内都更新换代来支持IPv6,因此在相对比较长的一段时期内,IPv6网络将和IPv4
通常一个HFC网络由前端(FE)、主数字终端(HDT)、光纤节点(FN)、网络接口单元(NIU)、综合业务单元(ISU)及传输线路等构成。根据HFC网接入Internet网的典型配置,将图6-12所示的拓扑图中(A)~(D)空缺处的名称填写完整(请使用题干
上述配置中是否有问题?请指出并说明理由。解释配置中画线部分内容含义?
图2给出了一个单位分配到的网络地址是217.14.8.0掩码是255.255.255.224。单位管理员将本单位的网络又分成了3个子网.如果你是网管人员:
阅读以下说明,回答问题1至问题5,将解答填入对应的解答栏内。HFC(HybirdFiber-coaxialcable,混合光纤同轴电缆网)接入技术是以现有的有线电视网(CATV)为基础,综合应用模拟和数字传输技术、射频技术和计算机技术所产生的一
在Linux操作系统下,可通过命令(2)显示路由信息。若主机所在网络的网关IP地址为192.168.0.254,则可使用命令(3)adddefault(4)192.168.0.254添加网关为默认路由。备选答案:A.nets
RSA是一种基于(31)原理的公钥加密算法。网络上广泛使用的PGP协议采用 RSA和IDEA 2种加密算法组成链式加密体系,这种方案的优点是(32)。PGP还可以对电子邮件进行认证,认证机制是用MD5算法产生(33)位的报文摘要,发送方用自己的RSA私钥对
两个公司希望通过Internet进行安全通信,保证从信息源到目的地之间的数据传输以密文形式出现,而且公司不希望由于在传输节点使用特殊的安全单元而增加开支,最合适的加密方式是(10),使用的会话密钥算法应该是(11)。
FrameRelayissimplifiedformof(66),similarinprincipleto(67),inwhichsynchronous,framesofdataareroutedtodifferent
随机试题
某女,56岁。心前区疼痛5年,每逢秋冬季加重,近半月时感心前区刺痛,且放射至左肩背部,伴心悸胸闷,舌质紫暗,脉细涩。辨证为
抛物线y2=4x与直线x=3所围成的平面图形绕x轴旋转一周形成的旋转体体积是()。
相对于直接融资来说,间接融资的信誉度较高,风险性相对较小,融资的稳定性较强。()
在美国、加拿大和英围,早餐麦片极受欢迎,是最盈利的行业之一。但是,在法国、德国、意大利以及其他很多国家,早餐麦片就不怎么受欢迎,利润也不高。这体现的是()。
美术是人类感受美、表现美和创造美的重要形式,也是表达自己对周围世界的认识和情绪态度的独特方式。()
下列说法不是杜威实用主义教育学论点的是()。
坚持中国特色新型工业化道路,就要做到()。
47,53,64,36,38,62,29,()
天气预报能为我们的生活提供良好的帮助,它属于计算机的()应用。
Anyphysicaltheoryisalwaysprovisional,inthesensethatitisonlyahypothesis;youcanneverproveit.Nomatterhowmany
最新回复
(
0
)