0

私が書いた次の貪欲なアルゴリズムに苦労しています。アルゴリズムが完全ではないことはわかっていますが、それを改善する方法は本当にわかりません.:

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" 個のライセンスを必要とします。特定の法律により、1 か月に複数の許可を取得することはできません。さらに、許可の費用は毎月増加します。実際、各許可証の費用は現在 $100.00 ですが、許可証 j, (1 ≤ j ≤ n) の費用は毎月 rj > 1 ずつ増加します (rj はパラメーターです)。つまり、最初の 4 か月でライセンスを購入すると 100r4 の費用がかかりますが、たとえば、5 か月でライセンスを取得するには 100(r3)^5 の費用がかかります。最後に、i が j と異なる場合、ri は rj とは異なると仮定します。問題は、与えられた rj (1 ≤ j ≤ n) のセットに対して、総所有コストを最小化するために "n" パーミットをどのような順序で購入するかです。1. この問題を解決するために、貪欲なアプローチを使用して多項式アルゴリズムを開発します。最悪の場合のアルゴリズムを分析します。2. アルゴリズムが最適解を適切に返すことを証明します。3. 次の場合のアルゴリズムを説明してください: n = 3、r1 = 3、r2 = 4、r3 = 2.

ありがとう

4

1 に答える 1

0 
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. では、このアルゴリズムの再帰的なバージョンをどのように記述すれば、今述べたことを検討できるようになるでしょうか? ありがとうございました。

于 2011-04-14T02:38:40.687 に答える