貪婪算法：成本最小化

我正在用我寫的貪婪算法掙扎;我知道我的算法是不完整的，但我真的不知道改進它：貪婪算法：成本最小化

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.00美元，但許可證j的成本（1≤j≤n）每月增加rj> 1（rj是參數）。換句話說，購買前四個月的許可費用爲100r4，而在第五個月的收購費用則爲100美元（r3）^ 5。最後，我們假設ri對於不同的j是不同的。接下來的問題是，對於一組給定的rj（1≤j≤n），以什麼順序購買「n」個許可證來最小化總體擁有成本。 1.使用貪婪方法開發多項式算法來解決這個問題。在最壞的情況下分析你的算法。 2.證明你的算法很好地返回最優解。 3.說明你在下列情況下的算法：N = 3，R1 = 3，R 2 = 4，R3 = 2

感謝

來源

2011-04-12 cProg

這顯然是一個家庭作業問題。請分享您嘗試過的內容，以及您正在努力解決的問題。您的算法在當前形式中沒有太大意義，因爲'j'是一個數字（在比較行上），但是它會變成下一行的許可證。 – 2011-04-12 23:45:18

大家好，直覺上，我可以說解決方案是首先選擇成本最高的rj。這是我的算法： 'code' 算法minCost（A [1 ... n]空表來存儲所選的許可證） while j cProg 2011-04-13 00:27:50

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-14 02:38:40 cProg

對不起？你能解釋更多嗎？我不明白什麼是「反例」。 – cProg 2011-04-14 02:58:58

nvm，正在考慮問題的一般化版本 – 2011-04-14 03:06:54

貪婪算法：成本最小化

回答

相關問題