首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
64
问题
阅读下列说明和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];
}
若5项物品的价值数组和重量数组分别为v[]={0,1,6,18,22,28)和w[]={0,1,2,5,6,7},背包容量为T=11,则获得的最大价值为
(7)
。
选项
答案
(7)40
解析
根据题干和C代码,得到下列c
的值。
从表中可知c[5][11]=40。
转载请注明原文地址:https://kaotiyun.com/show/hoxZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
请简要说出DHCP服务的基础流程?请分别写出在Linux系统中启动、停止和重新启动DHCP服务的3个命令。
设计布线时,需要考虑哪些主要因素?结构化布线应遵循的国际标准有哪些?
根据网络拓扑和需求说明,完成(或解释)路由器R1的配置。R1#configureterminal;进入全局配置模式R1(config)#interraceethernet0;进入端口配嗣模式R1(config-i
阅读以下说明,回答问题1至问题3,将解答填入对应的解答栏内。[说明]某单位网络的拓扑结构示意图如图5-1所示。该网络采用RIP协议,要求在R2上使用访问控制列表禁止网络192.168.20.0/24上的主机访问网络192.168.10.0/
假设在服务器和客户机之间均采用TCP/IP协议通信。请估算出在峰值时间点,该局域网上传输的数据的最小流量是多少?(请简要写出计算过程)在峰值时间,可能使用单独的CPU无法保证在规定的时间内完成各种应用。为了解决这个问题,需要增加CPU的数量。根据题
阅读以下说明,回答问题。(2011年下半年下午试题三)[说明]在windowsServer2003中可以采用筛选器来保护DNS通信。某网络拓扑结构如图4-86所示,WWW服务器的域名是www.shangxueba.com,DNS服务器上安装了Wind
SDLCwasinventedbyIBMtoreplacetheolderBisynchronousprotocolforwideareaconnectionsbetweenIBMequipment.Avarietio
FrameRelayissimplifiedformof(66),similarinprincipleto(67),inwhichsynchronous,framesofdataareroutedtodifferent
TraditionalIPpacketforwardinganalyzesthe(71)IPaddresscontainedinthenetworklayerheaderofeachpacketasthepacke
图(a)中只有一个外部实体E1。使用【说明】中的词语,给出E1的名称。在进行系统分析与设计时,面向数据结构的设计方法(如Jackson方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。
随机试题
若=_______
A.胰岛素治疗B.二甲双胍口服C.格列齐特口服D.单纯饮食控制下列糖尿病病人最佳治疗选择是:女性,35岁。已婚,未育。糖尿病病史5年。已停经56天,检查证实早孕。空腹血糖10mmol/L
六味地黄丸的配伍特点是()
按发行者的性质划分,金融工具可分为直接金融工具和间接金融工具,其中直接金融工具如企业、政府或个人发行和签署的商业票据、()以及抵押契约等。
企业的内部控制五要素中属于内部控制基础的是()。
资产风险管理模式强调商业银行最经常性的风险来自()。
根据相关材料,完成下列各题。材料一:酒泉市地形地貌示意图材料二:酒泉卫星发射基地位于内蒙古自治区辖区阿拉善盟,地处荒无人烟的巴丹吉林沙漠深处,海拔约1000米,这里是戈壁沙漠的一块小绿洲。它与酒泉市的直线距离超过200公里。材料三:
潘某不服某卫生局的行政处罚决定,向法院提起诉讼。诉讼过程中,卫生局撤销了原处罚决定,潘某遂向法院申请撤诉。法院作出准予撤诉的裁定。一周后,卫生局又以同一事实和理由作出了与原处罚决定相同的决定。下列哪一种说法是正确的?()
根据以下资料,回答下列问题。2011年1—7月,中国农产品进出口金额为833.3亿美元,同比增长28.9%。2011年7月,中国农产品进出口金额为130.3亿美元,环比增长10.4%,同比进出口金额增长30.1%。2011年1—7月,中
MywifeandIspenttwoweeksinLondonlastyear.Wewentthereinthe【11】WethinkitisthebestseasontovisitEngland.The
最新回复
(
0
)