algorithm - 诊断动态规划与优先级队列的情况

Question

我正在尝试确定是否可以使用 DP 或优先队列解决以下问题:

1) 我有一组对象。我的目标是在满足约束的同时选择足够多的分数给我最高分。

2) 每个对象的特征。每个对象都有一个分数和一个与之相关的深度。

3)约束:最终对象集合的深度总和必须<=100

例如

Index/Score/Depth (numbers below follow accordingly)

1 70 10

2 60 30

3 40 50

4 40 25

5 30 35

这些可能的输出可以是

Sum of Score/Sum of Depth (numbers below follow accordingly)

170 90 (i.e. Objects 1,2,3)

200 100 (i.e. Objects 1,2,4,5) -- the winner

130 90 (i.e. Objects 2,4,5)

150 85 (i.e. Objects 1,3,4)

140 95 (i.e. Objects 1,3,5)

以上表明贪婪的方法是行不通的，即总是取最高分或最低成本。例如，选择对象 4,5(总分 70，总深度 60)比只选择对象 3(得分 40 成本 50)要好。因此，直接的方法是行不通的，我需要探索我的整个搜索空间。所以似乎优先队列不起作用，是吗？ DP呢？有没有办法在这里应用动态规划？

Answer 1

所述问题是经典背包问题的重新表述，众所周知，该问题可通过动态规划求解。参见 this维基百科文章了解更多详情。使用优先级队列的方法很可能会导致贪心算法，可以对其进行细化以产生 2 近似值。更准确地说，元素可以按效率排序，贪婪地取走，直到下一个元素不再适合为止。然后从这个解决方案中获取更好的和最有利可图的项目。