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

admin2021-01-13 57

问题 (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

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