首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
53
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
给出域名解析的两种方案。当dns服务器发生故障,我们是否可以访问网络上的计算机?如果可以,需要什么条件?说明原因。
目前最流行的无线接入技术类型有哪几种?无线局域网可以在普通局域网基础上通过无线HUB、无线接入站(AccessPoint,AP,亦译作网络桥通器)、无线网桥、无线Modem及无线网卡等来实现。在业内无线局域网多种标准并存,太多的IEEE802.11标准
该企业网络的核心层采用了ATM技术,由3台ATM交换机互联构成。试对ATM网络技术的主要特点、协议分层结构和优点作简要叙述(控制在100个字以内)。图中用了两台路由器Router1,和Router2,简述路由器的技术特点,并说明Router1和Rou
下面是某路由器的部分配置信息,解释标有下划线部分的含义,将解答填入答题纸的对应栏内。[配置路由器信息]Currentconfiguration:!version11.3noservicepassword-en
请列举IEEE802.11b的两种工作模式。提高WLAN的安全性有哪些措施。
请回答以下有关组网的问题1~4,并把解答填入对应栏中。设有A、B、C、D4台主机都处在同一个物理网络中,A主机的IP地址是192.155.12.112,B主机的IP地址是192.155.12.120,C主机的IP地址是192.155.12.176,D主
阅读以下有关网络设备安装与调试的叙述,分析设备配置文件,回答问题1至问题3,把解答填入对应栏内。虚拟局域网(VirtualLAN)是与地理位置无关的局域网的一个广播域,由一个工作站发送的广播信息帧只能发送到具有相同虚拟网号的其他站点,可以形象地认
阅读以下说明,回答问题。(2011年上半年下午试题四)[说明]某公司两分支机构之间的网络配置如图3-11所示。为保护通信安全,在路由器router-a和router-b上配置IPSec安全策略,对192.168.8.0/24网段和192.168.
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(6
The purpose of the requirements definition phase is to produce a clear, complete, consistent, and testable(6)of the technical re
随机试题
治疗风痰眩晕和痰厥头痛的代表方剂是
100ml牛奶所产生的能量约为
A.代谢性酸中毒B.呼吸性酸中毒C.代谢性碱中毒D.呼吸性碱中毒E.以上都不是pH值下降,升高,PaCO2正常的是
A.结脉B.代脉C.促脉D.涩脉E.细脉
某公司在解散清算过程中,清算组通过编制资产负债表、清点登记公司财产后发现,公司财产不足以清偿债务。这种情况下,清算组应该如何处理?
项目风险的分解途径不包括()。
某银行推出某种贷款品种,该品种的利率每月根据市场利率调整一次,则该贷款属于()贷款。
岗位与薪酬的对应关系是线性关系的情况下,曲线越陡,说明()。
最高人民法院是国家的()。
把网络10.1.0.0/16进一步划分为子网10.1.0.0/18,则原网络被划分为____________个子网。
最新回复
(
0
)