首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
77
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
通过移动电话接入互联网采用的是什么交换技术,而打电话又是采用什么技术?进行一次查询的数据信息见表2,网络的基本通信服务费用见表3,总费用=网络租用费+通信费。根据表中给出的数据,试计算销售员每月至少应进行多少次查询,才能使得使用移动电话的总费用比使用P
在OSI参考模型有哪几层?NetBIOS包括哪些服务功能?
下面是某路由器的部分配置信息,解释标有下划线部分的含义,将解答填入答题纸的对应栏内。[配置路由器信息]Currentconfiguration:!version11.3noservicepassword-en
划分VLAN有哪几种划分方式?填充VLAN信息表,见表1,将答案填写在相应位置。
在WindowsServer2003的“路由和远程访问”中提供两种隧道协议来实现VPN服务:(1)和L2TP,L2TP协议将数据封装在(2)协议帧中进行传输。 为了加强远程访问管理,新建一条名为“SubInc”的访问控制策略,允许来自子公司服务器
在Linux系统中,DHcP服务默认的配置文件为:(1)。(1)备选答案:A./etc/dhcpd.confB./etc/dhcpd.configC./etc/dhcpc.confD./etc/dhcp.config管理员可
阅读以下说明,回答问题1至问题4,将解答填入对应的解答栏内。[说明]Linux系统有其独特的文件系统ext2,文件系统包括了文件的组织结构、处理文件的数据结构及操作文件的方法。可通过命令获取系统及磁盘分区状态信息,并能对其进行管理。以下命
阅读以下说明,回答问题。(2011年下半年下午试题三)[说明]在windowsServer2003中可以采用筛选器来保护DNS通信。某网络拓扑结构如图4-86所示,WWW服务器的域名是www.shangxueba.com,DNS服务器上安装了Wind
阅读以下说明,回答问题1至问题6,将解答填入答题纸对应的解答栏内。【说明】某单位网络拓扑结构如图3-1所示,其中Web服务器和DNS服务器均采用WindowsServer2008R2操作系统,客户端采用Windows操作系统,公司Web网站的域名
以下Windows命令中,可以用于验证端系统地址的是(56);可以用于识别分组传送路径的是(57);如果要终止一个ping会话,正确的操作是(58)。以下应用中,对网络带宽性能影响最大的应用是(59)。OSPF和RIP都是因特网中的路由协议,与RIP相比,
随机试题
对于大多数化学反应,升高温度,反应速率增大。()
不属于方剂运用变化的项是
给予肺炎高热患者降温处理时,正确的操作是
关于手足搐搦症的隐性体征正确的是
关于存货叙述正确的是( )。
甲市公安机关的法医董某,一天在送孩子去幼儿园的途中亲眼看见了李某抢劫王某,造成王某重伤,下列说法错误的有()。
(2017年真题)在某个时期内,个体对某种刺激特别敏感,过了这个时期,同样的刺激则影响很小或没有影响。这个时期称为()。
教师的医疗同当地国家公务员享受同等的待遇;()对教师进行身体健康检查,并因地制宜安排教师进行休养。
下图为我国4幅省级行政区域图,按图完成下列问题。少数民族中人数最多的民族所在的省级行政区域是()。
假设你是一个企业的质检员,厂里准备引进一台新设备,可以更好的提高生产力,你该怎么办?
最新回复
(
0
)