許可成本最小化算法

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，這個成本就會下降。因此，任何不以成本降序排列的解決方案都可以得到改進，最好的解決方案的確是按照成本的降序排列許可證。