Задача динамического программирования - PullRequest
Новая
       7

Задача динамического программирования

2 голосов
/ 29 апреля 2011

Ну, мне действительно не нужна помощь с самим кодом, но я понимаю, что именно я пытаюсь сделать, чтобы написать код.Вкратце, мне дано 1000 проектов, каждый из которых имеет набор ресурсов, и у меня есть (установленное количество) ресурсов, которые можно использовать для расчета лучших проектов, которые я могу выбрать.

псевдокод для лучшей прибылиФункция выглядит следующим образом:

bestProfit: 

Parameters - 
            projects: a vector of projects
            r:        the resources available to solve the subinstance 
            valueMap: the map data structure that is used for memoization
            n:        only projects numbered 0,...,n-1 may be 
                      used to solve the subinstance
Returns -   the maximum amount of profit that may be obtained on this
           subinstance of the optimization problem
Post-condition – If n > 0, then valueMap contains an entry 
                whose key is (r, n).

If n equals 0
     return 0
Check valueMap to see whether this subinstance has already been solved
-   If so, then return the previously computed result (function terminates)
best1 = bestProfit(projects, r, valueMap, n-1)
Check whether r provides enough resources to undertake project n-1
-   If so, then best2 = bestProfit(projects, r – projects[n-1].requirements, valueMap, n-1) 
+ projects[n-1].profit
 Else
     best2 = 0

If best1 >= best2
   Store (r, n) -> (best1, false) in valueMap
   Return best1
Else
   Store (r, n) -> (best2, true) in valueMap
   Return best2

Когда я выполняю рекурсивный вызов bestProfit, best1 должен проверять, разрешена ли уже подзадача.и best2, считается, что проверка осуществимости основана только на самом последнем проекте.другими словами это выглядит как сбалансированное дерево.Я не могу понять, как мне вставить значения на карту во время рекурсии?По сути, последнее утверждение if / else не произойдет, пока не будет пройден весь набор проектов.И только окончательное значение вставляется на мою карту.Я просто хочу несколько советов о том, как мне подходить к этому, чтобы правильно написать рекурсию.

Как я уже говорил ранее, я не ищу код, но способ понять требования этого псевдокода для моего проекта на C ++.именно эта логика сводит меня с ума в этот момент, потому что я не могу заставить ее работать вместе.Спасибо всем за то, что взглянули на это и предоставили лучшее понимание, если это возможно.

Ответы [ 2 ]

0 голосов
/ 19 мая 2012

Вы не используете нижний раствор?

Это прямое применение задачи Рюкзака с многочисленными эвристиками, применимыми к тому, чтобы сделать ее жадным решением, если дроби возможны ...

Для вашей задачи повторяемость - Пусть W -> некотораяПонятие, с помощью которого вы определяете, достаточно ли ваших ресурсов для
задачи 'k'. Пусть N -> набор задач, проиндексированных по 0-индексу. Пусть V -> 0, основанный индекс потенциальной прибыли для решения каждой проблемы OPT.[i] [j] = MAX (OPT [i-1] [j], OPT [i-1] [jW [i]] + V [i]), где «i» - индекс в списке проблем,j - это индекс того, сколько ресурсов еще доступно.Тогда ваше решение - OPT [размер [N]] [W]. Объяснение: интуитивно понятно, что подзадача заключается в выборе оптимального набора проектов из «i» с доступными ресурсами «j» ...

Рекурсия плохаяне допускает много оптимизаций компилятора с обычными вызовами функций.

0 голосов
/ 29 апреля 2011

Я бы вернул структуру данных, которая указывает как прибыль, так и решение, которое получает эту прибыль. Сохраните эту точную структуру данных в valueMap. Это сделает ваш код более простым.

По сути, «Напишите правильное рекурсивное решение. Добавьте памятку, чтобы сделать это быстро.»

...