首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
101
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
通常VLAN有哪两种实现方式。在基于端口的VLAN划分中,交换机上的每一个端口允许以哪3种模式划入VLAN中,并简述它们的含义。
该企业网络的核心层采用了ATM技术,由3台ATM交换机互联构成。试对ATM网络技术的主要特点、协议分层结构和优点作简要叙述(控制在100个字以内)。PC1~PC4按100Mbit/s的以太网协议运行,PC1和PC2划分在一个虚拟网之中(VLAN1),
阅读以下说明,回答问题,将解答填入对应栏内。网络地址转换(NAT)的主要目的是解决IP地址短缺问题以及实现TCP负载均衡等。在如图2所示的设计方案中,与Internet连接的路由器采用网络地址转换。请根据路由器的NAT表和图2中给出的网络结构、
阅读以下有关传统局域网络运行和维护的叙述,将应填入(n)处的字句写在对应栏内。在对网络运行及维护前首先要了解网络,包括识别网络对象的硬件情况、判别局域网的拓扑结构和信道访问方式、确定网络互联以及用户负载等。常见的3种拓扑结构是星形、(1)与(2)拓扑结
在Linux系统中,DHcP服务默认的配置文件为:(1)。(1)备选答案:A./etc/dhcpd.confB./etc/dhcpd.configC./etc/dhcpc.confD./etc/dhcp.config在Lin
该网络采用核心层、汇聚层、接入层的三层架构。根据层次化网络设计的原则,数据包过滤、协议转换应在(11)层完成;(12)层提供高速骨=F线路;MAC层过滤和IP地址绑定在(13)层完成。(13)
在Linux操作系统下,可通过命令(2)显示路由信息。若主机所在网络的网关IP地址为192.168.0.254,则可使用命令(3)adddefault(4)192.168.0.254添加网关为默认路由。备选答案:A.gat
访问控制表是防火墙实现安全管理的重要手段。完成下列访问控制列表(access-control-list)的配置内容,使内部所有主机不能访问外部IP地址段为202.117.12.0/24的Web服务器。Firewall(config)#access-
阅读以下说明。回答问题,将解答填入答题纸对应的解答栏内。【说明】某公司网络划分为两个子网,其中设备A是DHCP服务器,如图3-1所示。如果客户机无法找到DHCP服务器,它将从________________网段中挑选一个作为自己的IP地址,子网掩
MultipurposeInternetMailExtension(MIME)is a(46)document messaging standard in the Internet enviroment, with MIME, users can
随机试题
淋巴性肿胀
简述臀大肌的起止和作用。
患者男,59岁。因急起兴奋,乱语,情绪不稳1天入院。患者1天前无明显原因突起兴奋话多,胡言乱语,自言自语,不停的说话,诉有人要害他,看见汽车就认为是要来抓他的,有时说听见有人在喊他让他认罪。情绪不稳定,紧张恐惧,躲在床上蒙着头,易激惹,无故骂人。夜不眠。体
A.急性出血性胰腺炎B.先天性胆管扩张症C.急性梗阻性化脓性胆管炎D.急性化脓性胆管炎E.急性憩室炎Murphy征出现在
患者,女,51岁。胁肋灼痛,面红目赤,口干口苦,耳鸣如潮,大便秘结,舌红苔黄,脉弦数。其辨证为
()是组织各级管理层所追求的目标。
某城市2009年前三季度商品房销售均价分别为5123元/m2,5480元/m2,5920元/m2,则该市第三季度商品房销售均价环比增长率为()。
建设工程项目施工成本偏差是指( )之差。
进行证券投资技术分析的假设中,从人的心理因素方面考虑的假设是()。
∫sec3xdx=________.
最新回复
(
0
)