首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
54
问题
阅读下列说明和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://jikaoti.com/ti/JTa7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
随着Internet的发展,用户对网络带宽的要求不断提高,传统的接入网已成为整个网络中的瓶颈,以新的宽带接入技术取而代之已成为目前研究的焦点。其中最引人注意的是光纤接入技术。
某小公司的网络拓扑结构如图4所示。其中路由器具有ISDN模块,公司网络通过ISDN连接到ISP。
在由L2TP构建的VPN中,主要由(1)和(2)两种类型的服务器构成。1.将图2中(1)和(2)处空缺名称填写在答题纸的相应位置。2.相对于L2TP,另一种构建VPN的方式是什么?某路由器(在图2中没有标出)的部分配置信息如下所示,请解
目前,国内短消息服务平台按照接入方式主要可分为哪两种?请简要说出网关服务器与短消息服务过程。
图中(a)、(b)、(c)、(d)为不同类型IPSee数据包的示意图,其中(1)和(2)工作在隧道模式;(3)和(4)支持报文加密。R2与Rl之间采用预共享密钥“12345678”建立IPSec安全关联,请完成下面配置命令。Rl(eonfig)#c
在Linux中,分区分为主分区、扩展分区和逻辑分区,使用fdisk-1命令获得分区信息如下所示:Disk/dev/hda:240heads,63sectors,1940cylindersUnits=cyliridersof1
阅读以下说明,回答问题。(2011年上半年下午试题四)[说明]某公司两分支机构之间的网络配置如图3-11所示。为保护通信安全,在路由器router-a和router-b上配置IPSec安全策略,对192.168.8.0/24网段和192.168.
MultipurposeInternetMailExtension(MIME)is a(46)document messaging standard in the Internet enviroment, with MIME, users can
两个公司希望通过Internet传输大量敏感数据,从信息源到目的地之间的传输数据以密文形式出现,而且不希望由于在传输结点使用特殊的安全单元而增加开支,最合适的加密方式是(),使用会话密钥算法效率最高的是()。
随机试题
A.骨软骨瘤B.骨巨细胞瘤C.骨肉瘤D.骨转移癌E.骨囊肿男,28岁,右膝内侧逐渐隆起,伴隐痛半年。X线片示:右胫骨干骺端有一破坏区,边缘呈膨胀性改变中央有“肥皂泡”样阴影。诊断首先考虑
A.蛋白质变性B.蛋白质变构C.核酸变性D.蛋白质沉淀E.核酸沉淀某些理化因素作用下,多肽链高级结构破坏,生物学活性丧失属于
工程竣工结算分为()。
发电机转子穿装前应单独进行()。
沥青混合料的松铺系数的确定方法是()。
刘某出资12万元设立了一个一人有限责任公司。公司存续期间,刘某的下列行为中,符合公司法律制度规定的是()。(2009年)
上海黄金交易所实行()组织形式。
习近平主席在博鳌亚洲论坛2018年年会开幕式上发表主旨演讲时指出,实践证明过去40年中国经济发展是在开放条件下取得的,未来中国经济实现高质量发展也必将在更加开放的条件下进行。在扩大开放方面,中国将采取的重大举措包括()。
教材编写、教学、评估和考试命题的依据是()。
南方重建
最新回复
(
0
)