许可成本最小化算法

Question

假设您拥有一家必须许可软件模块的公司。您每个月只能购买一个许可证。软件许可证的成本完全不同，由p1，pn给出。所有许可证的成本每月增加一个因子r（r> 1）。因此，在第m个月后，第i个产品的许可证的价格为pi * r^m 。设计一个n日志n算法，以找出订购 购买许可证的次数，以最大限度地降低公司的总成本。

我的第一个解决方案是首先订购最昂贵的许可证，因为它们的成本将会增加最快。然而，答案对我来说太简单了。我在想这个错吗？

Answer 1

解决这样一个问题的一部分就是证明您提出的解决方案实际可行。根据您在问题中所说的内容，可以尝试以下方法：

假设最佳解决方案不按照成本降序排列许可证。在假设的解决方案中，用Xi < Xj和i < j取两个许可证Xi，Xj。现在交换它们。其他许可的成本不变。这两个许可证的成本从Xi * r^i + Xj * r^j变为Xi * r^j + Xj * r^i，只要r> 1，这个成本就会下降。因此，任何不以成本降序排列的解决方案都可以得到改进，最好的解决方案的确是按照成本的降序排列许可证。