首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
75
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
给出域名解析的两种方案。当dns服务器发生故障,我们是否可以访问网络上的计算机?如果可以,需要什么条件?说明原因。
如图4所示,GSW为千兆以太网交换机,内设ATM模块。SW1为100M/1000Mbit/s以太网交换机,SW2为ATM/100Mbit/s以大网交换机,RT为中心路由器;S1和S2为服务器,分别经千兆以太网卡和155Mbit/sATM网卡与GSW(千兆以
阅读以下说明,回答问题,将解答填入对应栏内。网络地址转换(NAT)的主要目的是解决IP地址短缺问题以及实现TCP负载均衡等。在如图2所示的设计方案中,与Internet连接的路由器采用网络地址转换。请根据路由器的NAT表和图2中给出的网络结构、
请你分配合适的子网地址,要求地址不能浪费。分配路由器R1、R2的内网接口的中和掩码。
阅读以下说明,回答问题1至问题5,将解答填入对应的解答栏内。HFC(HybirdFiber-coaxialcable,混合光纤同轴电缆网)接入技术是以现有的有线电视网(CATV)为基础,综合应用模拟和数字传输技术、射频技术和计算机技术所产生的一
在Linux系统中,DNS查询文件内容如下所示,该文件的默认存储位置为(5),当用户做DNS查询时,首选DNS服务器的IP地址为(6)。Serachdomain.test.cnNameserver210.34.0.14
阅读以下说明,回答问题1至问题4,将解答填入对应的解答栏内。[说明]Linux系统有其独特的文件系统ext2,文件系统包括了文件的组织结构、处理文件的数据结构及操作文件的方法。可通过命令获取系统及磁盘分区状态信息,并能对其进行管理。以下命
在Linux中,分区分为主分区、扩展分区和逻辑分区,使用fdisk-1命令获得分区信息如下所示:Disk/dev/hda:240heads,63sectors,1940cylindersUnits=cyliridersof1
FrameRelayissimplifiedformof(66),similarinprincipleto(67),inwhichsynchronous,framesofdataareroutedtodifferent
X.509证书标准是一种由发布者数字签名的用于绑定(1)和其持有者身份的数据结构。发布者是证书的颁发者,它(2);(3)和公开密钥的绑定是证书的核心内容。它们的绑定是通过(垒)实现的。(1)
随机试题
简述新闻采访的基本任务。
管理
急性心肌梗死出现以下哪些心律失常提示有发生心室颤动的危险
患者,男,40岁。有上腹受伤致肝破裂。意识清楚,上腹部明显压痛,面色苍白,四肢湿冷,脉搏130次/分,血压80/60mmHg,尿少,口渴,过度换气。立即给患者快速补充血容量,宜首先输注
近年来,导致全球交易所由会员制向公司制发展的因素有()。
以技术分析为基础的投资策略是在否定弱势有效市场的前提下,以历史交易数据为基础的调查研究模型。()
以下物权可以在同一物并存的是()。
下列各句中没有语病的一句是()。
新闻出版总署有关负责人的表态,让一度______的“记者黑名单”风波,有了一个官方定论。这位负责人说:“对新闻媒体存在的报道内容个别细节不准确的问题,不应该采取求全责备的态度。”新闻出版总署的表态,值得多方______。依次填入画横线部分最恰当的一项是(
中断是CPU与外部设备数据交换的重要方式。CPU响应中断时必须具备三个条件,分别为:外部提出中断请求;本中断未屏蔽;(4)。CPU响应中断后,必须由(5)提供地址信息,引导程序进入中断服务子程序:中断服务程序的入口地址存放在(6)中。
最新回复
(
0
)