贪婪算法:成本最小化
贪婪算法:成本最小化
提问于 2011-04-13 07:23:11
我正在努力使用我写的以下贪婪算法；我知道我的算法不完整，但我真的不知道如何改进它。
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是参数)。1.提出了一种基于贪心方法的多项式算法，用于求解该问题。在最坏的情况下分析你的算法。2.证明你的算法很好地返回了最优解。3.在以下实例上说明您的算法:n= 3，r1 = 3，r2 = 4，r3 = 2。
谢谢
回答 1
Stack Overflow用户
发布于 2011-04-14 10:38:41
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的完整部分。那么，我如何编写此算法的递归版本，以允许我考虑刚才提到的内容？谢谢。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5642758
复制相关文章
相似问题
腾讯云开发者
