简答题

一般背包问题的贪心算法可以获得最优解吗?物品的选择策略是什么?

正确答案

按照p[i]/w[i]≥p[i+1]/w[i+1]排序,选择当前利润/重量比最大的物品,可以获得最优解。

答案解析