Жадные алгоритмы: минимизация затрат - PullRequest
Новая
       6

Жадные алгоритмы: минимизация затрат

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

Я борюсь со следующим жадным алгоритмом, который я написал; Я знаю, что мой алгоритм не завершен, но я действительно не знаю, как его улучшить. 

Algorithme minCost()

while j<n (while all the licences have not been yet bought)
j=next licence bought
If the licence of the current month is available then
buy
EndIf
EndWhile

Это постановка задачи: Чтобы продавать свои различные продукты, компании нужны «n» лицензии. Из-за определенных законов, он не может получить более одного разрешения в месяц. Кроме того, стоимость путевок увеличивается каждый месяц. Действительно, хотя стоимость каждого разрешения в настоящее время составляет 100 долларов США, стоимость разрешения j (1 ≤ j ≤ n) увеличивается с коэффициентом rj> 1 каждый месяц (rj являются параметрами). Другими словами, покупка лицензии в течение первых четырех месяцев стоит 100р4, в то время как ее приобретение в течение пятого месяца, например, будет стоить $ 100 (р3) ^ 5. Наконец, мы предполагаем, что ri отличается от rj для i, отличного от j. Тогда возникает вопрос, для какого набора rj (1 ≤ j ≤ n), в каком порядке покупать разрешения «n», чтобы минимизировать общую стоимость владения. 1. Разработайте полиномиальный алгоритм, используя жадный подход, для решения этой проблемы. Проанализируйте свой алгоритм в худшем случае. 2. Докажите, что ваш алгоритм хорошо возвращает оптимальное решение. 3. Проиллюстрируйте свой алгоритм на следующем примере: n = 3, r1 = 3, r2 = 4, r3 = 2.

Спасибо

1 Ответ

0 голосов
/ 14 апреля 2011 
Algorithme minCout(A[1, ..., n], B[])
//A[1, ..., n]: table storing the rj values of the licenses cost
//B[]: empty table to store selected licences cost for buy
QuickSort(A[1, ..., n])
//A[1, ..., n] is now sorted in decreasing order

 while j < n (while all the licences have not been yet bought) do
    for i ← 1 to n (Check all the available licences cost) do
    if ri < ri+1 (choose the highest license cost) then
    A[i ] = i + 1 (buy now the highest cost licence)
    end
    j = j + 1 (check the next licence to buy)
    end
    end
Return A[i]

Обычно количество лицензий должно уменьшаться по мере того, как я выбираю лицензии с наивысшей стоимостью и сохраняю их в таблице B. Кроме того, поскольку я проверяю стоимость лицензий, я не долженеще раз просмотрите полную часть таблицы A. Затем, как я могу написать рекурсивную версию этого алгоритма, которая может позволить мне рассмотреть то, что я только что упомянул?Спасибо.

...