(2013年上半年上午试题60、61)考虑下述背包问题的实例。有5件物品，背包容量为100，每件物品的价值和重量如表9．2所示，并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中，则采用了________(60)设计策略

admin2021-01-13 34

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

(60)

选项 A、分治
B、贪心
C、动态规划
D、回溯

答案B

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

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】给定一个字符序列B=b1b2…bn，其中bi∈{A，C，G，U}。B上的二级结构是一组字符对集合S={(bi，bj)}，其中i，j∈{1，2，…，n}，并满足

试述我国政权组织形式与国家性质之间的关系。

人们在未知领域内进行的开创性活动，且无固定程序与章法可遵循的实践是指

在项目决策与分析的初步可行性研究阶段，估算项目所需人员属于()的内容。

我国“十一五”规划中的量化指标主要分为预期性指标和约束性指标两类，以下那些属于是预期性指标()。

按照是否有担保划分，同业拆借可以分为()。

纸张：印刷：书籍

"I’vebeenexpectingyou!"Marekrepeated,whenhehadseatedhisguestinacomfortableleatherchair.Nothingonearthwould

曲线L：(a＞0)在t＝π／2对应点处的曲率为________．

During　the　last　few　years　,it　has　been　realized　that　maintenance　of　programs　is　more　expensive　than　development,　so　reading　of　p

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

软考中级

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】给定一个字符序列B=b1b2…bn，其中bi∈{A，C，G，U}。B上的二级结构是一组字符对集合S={(bi，bj)}，其中i，j∈{1，2，…，n}，并满足

试述我国政权组织形式与国家性质之间的关系。

人们在未知领域内进行的开创性活动，且无固定程序与章法可遵循的实践是指

在项目决策与分析的初步可行性研究阶段，估算项目所需人员属于()的内容。

我国“十一五”规划中的量化指标主要分为预期性指标和约束性指标两类，以下那些属于是预期性指标()。

按照是否有担保划分，同业拆借可以分为()。

纸张：印刷：书籍

"I’vebeenexpectingyou!"Marekrepeated,whenhehadseatedhisguestinacomfortableleatherchair.Nothingonearthwould

曲线L：(a＞0)在t＝π／2对应点处的曲率为________．

During the last few years ,it has been realized that maintenance of programs is more expensive than development, so reading of p

During　the　last　few　years　,it　has　been　realized　that　maintenance　of　programs　is　more　expensive　than　development,　so　reading　of　p