题目
8.采用贪心法求解”部分背包问题“时,所采用的贪心策略是( )(单选题)A.价值最大的优先装包B.价值最小的优先装包C.价值密度最大的优先装包D.体积最小的优先装包
8.采用贪心法求解”部分背包问题“时,所采用的贪心策略是( )(单选题)
A.价值最大的优先装包
B.价值最小的优先装包
C.价值密度最大的优先装包
D.体积最小的优先装包
题目解答
答案
在解决“部分背包问题”时,所采用的贪心策略是 C. 价值密度最大的优先装包。
部分背包问题允许将物品分割成任意比例,因此贪心算法会选择价值密度(单位体积价值)最大的物品优先装入背包。这是因为通过优先选择价值密度高的物品,可以在有限的背包容量内获得尽可能高的总价值。
A. 价值最大的优先装包:只考虑物品的绝对价值而不考虑体积,这种策略不适用于部分背包问题。
B. 价值最小的优先装包:不符合部分背包问题的贪心策略。 D. 体积最小的优先装包:只考虑体积而不考虑价值密度,也不适用于部分背包问题。
因此,正确的贪心策略是 C. 价值密度最大的优先装包。