首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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];
}
根据说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下关于网络应用系统模块测试的技术说明,根据要求回答问题1至问题4。【说明】某公司的枝术开发小组经过一年的努力,编码完成了本公司嵌入式产品——宽带路由器的NanOs程序,该程序规模约为31200行。公司经理指定郭工程师(以下简称为郭工)安排其
如何根据网络流量选择联网设备,给出所选设备的作用?在我国,目前可供选择大的用户选择的接入方式有哪些,各自的接入速率为多少?
ISP是什么?请举例。在路由器和ISDN之间需要加入终端适配器(TA)吗?试说明在什么情况下需要加入TA。
设计布线时,需要考虑哪些主要因素?布线实施后,需要经过系统测试,测试线路的主要指标有哪些?
请列举IEEE802.11b的两种工作模式。提高WLAN的安全性有哪些措施。
划分VLAN有哪几种划分方式?填充VLAN信息表,见表1,将答案填写在相应位置。
设置ServerA和ServerB之间通信的筛选器属性界面如图4-2所示,在ServerA的IPSec安全策略配置过程中,当源地址和目标地址均设置为“一个特定的IP子网”时,源子网IP地址应设为(7),目标子网IP地址应设为(8)。图4-3
Multipurpose Internet MaiI Extension (MIME) is a(71)document messaging standard in the Internet enviroment, with MIME, users can
SDLC was invented by IBM to replace the older Bisynchronous protocol for wide area connections between IBM equipment. A varietio
栈是一种按“后进先出”原则进行插入和删除操作的数据结构,因此,______必须用栈。
随机试题
2013年3月18日,甲机械公司与乙融资租赁公司接洽融资租赁某型号数控机床事宜。同年4月1日,乙按照甲的要求与丙精密设备公司签订了购买1台某型号数控机床的买卖合同。丁以乙的保证人身份在该买卖合同上签字,但合同中并无保证条款,丙和丁亦未另行签订保证合同。乙和
欲提高血中HCO3-5mmol/L,应选择:()
可接受A型血的包括
桑叶具有的功效是
一个工人被派去打扫溅出的白色粉末,后发现其出现呼吸困难和惊厥,通过检测发现白色粉末为鱼藤酮,鱼藤酮抑制
具有审查效果好、时间短等优点,但仅适用于采用标准图纸的工程预算审查方法是()。
标志着国际银行业的全面风险管理原则体系基本形成的是()的出台。
由于所有者权益和负债都是对企业资产的要求权,因此它们的性质是一样的。()
下列表述中,属于房地产市场供给特点的是()。
填入下列语句横线中的词最恰当的一项是()。天下着__________的雨,听得见石川河水在哗哗流淌。擦去窗玻璃上凝满的水汽,我贪婪地往外看,山冈上烟雨迷离,树木葱茏,显出新开垦的痕迹。那些树行距规整,高矮相当,长得__________,_
最新回复
(
0
)