首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
49
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
NAT英文全称是"NetworkAddressTranslation",中文意思是“网络地址转换”,它是一个IETF(InternetEngineeringTaskForce,Internet工程任务组)标准,允许一个整体机构以一个公用IP(I
一台Windows2003操作系统的主机上同时安装了IPv6和IPv4两种协议,该主机既可以和仅支持IPv4协议的主机通信,也可以和仅支持IPv6协议的主机通信,这种实现IPv4向IPv6的平稳过渡的通信方案称为双协议栈技术。基于该技术的协议栈结构如图7
划分VLAN有哪几种划分方式?在VLAN中,STP和VTP是什么协议?各有什么作用?
阅读以下说明,回答问题1~7,将解答填入对应的解答栏内。图3-1是在网络中划分VLAN的连接示意图。VLAN可以不考虑用户的物理位置,而根据功能、应用等因素将用户从逻辑上划分为一个个功能相对独立的工作组,每个用户主机都连接在支持VLAN的交换机端口
阅读以下说明,回答问题1至问题5,将解答填入对应的解答栏内。HFC(HybirdFiber-coaxialcable,混合光纤同轴电缆网)接入技术是以现有的有线电视网(CATV)为基础,综合应用模拟和数字传输技术、射频技术和计算机技术所产生的一
阅读以下说明,回答问题1至问题5,将解答填入对应的解答栏内。[说明]某公司两分支机构之间的网络配置如图4-1所示,为保护通信安全,在路由器router-a和router-b上配置IPSec安全策略,对192.168.8.0/24网段和192
访问控制表是防火墙实现安全管理的重要手段。完成下列访问控制列表(access-control-list)的配置内容,使内部所有主机不能访问外部IP地址段为202.117.12.0/24的Web服务器。Firewall(config)#access-
阅读以下说明,回答问题1至问题6,将解答填入答题纸对应的解答栏内。【说明】某单位网络拓扑结构如图3-1所示,其中Web服务器和DNS服务器均采用WindowsServer2008R2操作系统,客户端采用Windows操作系统,公司Web网站的域名
在网络的拓扑结构中,处于上层的结点称为(36)。只要有一个结点发生故障,网络通信就无法进行的结构是(37);数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。
访问控制列表access-list109denyip10.1.0.00.0.255.255anyeq80的含义是:(58)。
随机试题
以下哪个不是孤独症的高危因素
监理单位接受建设单位委托对工程项目实施全过程监理时,需要在设计准备阶段( )。
会计科目按其所()不同,分为总分类科目和明细分类科目。
某公司经营规模迅速扩张,但由于人员储备不足,造成很多重要岗位无人填补,这说明该公司的()工作没有做好。(2008年真题)
甲股份有限公司(以下简称“甲公司”)为一家从事贵金属进口、加工生产及相关产品销售的企业,其2×15年发生了下列交易或事项:(1)为促进产品销售,甲公司于2×15年推出贵金属产品以旧换新业务。甲公司在销售所生产的黄金饰品时,承诺客户在购买后任一时点,若
中华人民共和国16周岁以上的公民普通护照有效期一般为()年。
(1)新来的年轻鸬鹚突然集体罢工,不肯下海(2)老鸬鹚因为老得不能出海了,被杀掉炖汤(3)渔夫百思不得其解,抱怨自己待它们不薄(4)一群鸬鹚,辛辛苦苦跟着一位渔夫十几年(5)因为老了,还不落个老鸬鹚一样的下场?
窗体上有1个名称为Commandl的命令按钮,事件过程如下:PrivateSubCommandl_Click()DimhumAsInteger,xAsIntegernum:Val(InputBox(“请输入一个正整数”))Selec
Whyisthewomancalling?
Cultureisactivityofthought,andreceptivenesstobeautyandhumanefeeling.【1】ofinformationhavenothingtodowithit.Am
最新回复
(
0
)