algorithm - 贪心算法 - 折旧成本

Question

这是我在 Kleinberg 和 Tardos 的算法设计中作为额外注释发现的一个问题。

假设我们试图出售其成本以每月r _{i < 1 的因子贬值的设备，从 100 美元开始，所以如果你在 t 个月后出售它，你将获得 100.r i} ^t。

如果您每个月只能出售一件商品，那么出售它们的最佳顺序是什么？

输入（3/4；1/2；1/100）

最佳顺序是 [100x{1/2+(3/4) ² +(1/100) ³ }]。

我不知道如何解决这个问题。

Answer 1

假设有 N 项具有单独的 Ri。

1. 计算 N x N 矩阵，其中 Cij = Power(Ri,j)。

2. 现在问题归结为分配问题，其中 N 个对象被放置在 N 个位置，每个位置都有相应的利润。

3. 使用任何算法（如匈牙利算法）最大化总利润。

Answer 2

贪婪的方法应该有效。每个月销售最大化 Ri^month - Ri^(month+1) 的项目。这意味着我们会出售下个月会损失最大价值的物品。

在示例输入中：

• 1/2 ^ 1 - 1/2 ^ 2 = 0.25
• 3/4 ^ 1 - 3/4 ^ 2 = 0.1875
• 1/100 ^ 1 - 1/100 ^ 2 = 0.0099

所以第一个月我们销售 R = 1/2 的商品

• 3/4 ^ 2 - 3/4 ^ 3 = 0.046875
• 1/100 ^ 2 - 1/100 ^ 3 = 0.000099

R = 3/4 作为第二项，1/100 作为最后一项。

我不是数学家，所以我不能给你证明，但很明显，如果你接受形式为 a^xa^(x+1) = b^xb^(x+1) 的函数只有一种解决方案。