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”个许可证。由于某些法律，它每月不能获得超过一个许可证。此外，许可证的成本每月都在增加。事实上，虽然目前每个许可证的成本为 100.00 美元，但许可证 j (1 ≤ j ≤ n) 的成本每月增加 rj> 1 倍（rj 是参数）。换句话说，例如，在前四个月购买许可证的费用为 100r4，而在第五个月购买许可证的费用为 100(r3)^5 美元。最后，我们假设 ri 与 rj 不同，因为 i 与 j 不同。那么问题是，对于给定的一组 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 回答