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 回答