Диагностирование динамического программирования против ситуации очередей приоритетов

Question

Я пытаюсь определить, если следующий может быть решена с помощью DP или приоритет очереди:

1) У меня есть набор объектов. Моя цель - выбрать достаточно их, чтобы дать мне самый высокий балл, выполняя ограничение.

2) Характеристика каждого объекта. Каждый объект имеет оценку и глубину, связанные с ним.

3) Ограничение: сумма глубин от возможного множества объектов должен быть < = 100

Например

Индекс/счет/Глубина (цифры ниже следуют соответственно)

Возможный Выход из них может быть

Сумма Score/Сумма Глубина (цифры ниже следуют соответственно)

170 90 (т.е. Предметы 1,2,3)

200 100 (т.е. объектов 1,2,4,5) - победитель

130 90 (т.е. объекты 2,4,5)

150 85 (то есть объекты 1,3,4)

140 95 (т.е. объекты 1,3,5)

Приведенные выше показывает, что жадный подход не будет работать, т.е. всегда принимает самый высокий балл или низкую стоимость , Например, взятие предметов 4,5 (общий балл 70, общая глубина 60) лучше, чем просто объект 3 (оценка 40 стоит 50). В результате этого простой подход не будет работать, мне нужно изучить все пространство поиска. Таким образом, кажется, что очередь приоритетов не будет работать, не так ли? Как насчет DP? Есть ли способ применить динамическое программирование здесь?

Answer 1

Указанная проблема представляет собой переформулировку классической проблемы Рюкзака, которая, как известно, разрешима динамическим программированием. См. Статью this Wikipedia для более подробной информации. Подход с использованием очереди приоритетов, скорее всего, приведет к жадному алгоритму, который можно уточнить, чтобы получить 2-приближение. Точнее, элементы можно сортировать по эффективности и воспринимать с жадностью, пока следующий элемент больше не подходит. Затем возьмите лучшее из этого решения и самый выгодный предмет.