考虑下述背包问题的实例。有5件物品，背包容量为100，每件物品的价值和重量如图8一11所示，并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中，则采用了(60)设计策略。考虑0／1背包问题(每件物品或者全部装入背包或者不

admin2019-07-12 29

问题考虑下述背包问题的实例。有5件物品，背包容量为100，每件物品的价值和重量如图8一11所示，并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中，则采用了(60)设计策略。考虑0／1背包问题(每件物品或者全部装入背包或者不装入背包)和部分背包问题(物品可以部分装入背包)，求解该实例得到的最大价值分别为(61)。

(61)

选项 A、605和630
B、605和605
C、430和630
D、630和430

答案C

解析本题考查贪心算法和背包问题的知识点。贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。采用0／1背包考虑该问题时，只能放入1、2、3号物品，故总价值为430，采用部分背包可以将物品拆分，故放入1、2、3号物品后还可以将编号4的物品部分的装入，使得背包容量尽量的满，故总容量为630。

转载请注明原文地址:https://kaotiyun.com/show/I6CZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

在进行进度安排时，PERT图不能清晰的描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、……、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2)

若在系统中有若干个互斥资源R，6个并发进程，每个进程都需要2个资源R，那么使系统不发生死锁的资源尺的最少数目为__________。(2010年上半年试题)

在Windows98操作系统中，TCP／IP是以__________方式实现的。

某主机本地连接属性如下图所示，下列说法中错误的是__________。(2012年下半年试题)

假设有证书发放机构I1、I2，用户A在I1获取证书，用户B在I2获取证书，I1和I2已安全交换了各自的公钥，如果用I1《A》表示由I1颁发给A的证书，A可通过()证书链获取B的公开密钥。

物联网中使用的无线传感网络技术是____________。

某文件系统采用位示图(bitmap)记录磁盘的使用情况。若计算机系统的字长为64位，磁盘的容量为1024G，物理块大小为4MB，那么位示图的大小需要()个字。

阅读以下说明和c++码，将应填入(n)处的字名写在的对应栏内。[说明]以下函数完成求表达式的值，请填空使之完成此功能。floatsum(floatx){floats=0.0;ints

食管癌患者出现持续性胸背痛多表示()。

臀位分娩时，产程中的处理正确的是

选举法规定，在直接选举中，正式代表候选人名单应当在选举之前公布。下列选顷哪个是正确的公布日期?()

老年人在孙辈教育中的弱势主要表现在()。

关于社会运动的两种基本形式，表述正确的是()。

学生是教育活动的对象，根据学生自身特点可以看出，学生具有可塑性、_和_。

DRAM是靠MOS电路中的栅极电容上的电荷来记忆信息的。为了防止数据丢失，需定时给电容上的电荷进行补充，这是通过以一定的时间间隔将DRAM各存储单元中的数据读出并再写入实现的，该过程称为DRAM的【　　】。

计算并填写下表：【5】

软件设计师上午基础知识考试

软考中级

在进行进度安排时，PERT图不能清晰的描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、……、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2)

若在系统中有若干个互斥资源R，6个并发进程，每个进程都需要2个资源R，那么使系统不发生死锁的资源尺的最少数目为__________。(2010年上半年试题)

在Windows98操作系统中，TCP／IP是以__________方式实现的。

某主机本地连接属性如下图所示，下列说法中错误的是__________。(2012年下半年试题)

假设有证书发放机构I1、I2，用户A在I1获取证书，用户B在I2获取证书，I1和I2已安全交换了各自的公钥，如果用I1《A》表示由I1颁发给A的证书，A可通过()证书链获取B的公开密钥。

物联网中使用的无线传感网络技术是____________。

某文件系统采用位示图(bitmap)记录磁盘的使用情况。若计算机系统的字长为64位，磁盘的容量为1024G，物理块大小为4MB，那么位示图的大小需要()个字。

阅读以下说明和c++码，将应填入(n)处的字名写在的对应栏内。[说明]以下函数完成求表达式的值，请填空使之完成此功能。floatsum(floatx){floats=0.0;ints

食管癌患者出现持续性胸背痛多表示()。

臀位分娩时，产程中的处理正确的是

选举法规定，在直接选举中，正式代表候选人名单应当在选举之前公布。下列选顷哪个是正确的公布日期?()

老年人在孙辈教育中的弱势主要表现在()。

关于社会运动的两种基本形式，表述正确的是()。

学生是教育活动的对象，根据学生自身特点可以看出，学生具有可塑性、_______和_______。

DRAM是靠MOS电路中的栅极电容上的电荷来记忆信息的。为了防止数据丢失，需定时给电容上的电荷进行补充，这是通过以一定的时间间隔将DRAM各存储单元中的数据读出并再写入实现的，该过程称为DRAM的【 】。

计算并填写下表：【5】

学生是教育活动的对象，根据学生自身特点可以看出，学生具有可塑性、_和_。

DRAM是靠MOS电路中的栅极电容上的电荷来记忆信息的。为了防止数据丢失，需定时给电容上的电荷进行补充，这是通过以一定的时间间隔将DRAM各存储单元中的数据读出并再写入实现的，该过程称为DRAM的【　　】。