我正在为我编写的以下贪心算法而苦苦挣扎;我知道我的算法不完整,但我真的不知道如何改进它。:
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。
谢谢