0

假设我们有 10 美元的初始财富，我们想通过买卖土豆来赚钱，并且以一种神奇的方式，我们知道每种土豆香料每年每公斤的价格 ($)。找到最终最大财富或局部最大值的最佳算法是什么？

！！如果您有 15 美元的财富，并且您在一年内卖出了一些公斤并赚了 4 美元，那么您不能在同一年购买 19 美元的东西，他们是独立的，所以您应该有钱在卖之前买东西同一年的其他事情！

例如

起始财富：10美元

每年每公斤马铃薯香料的价格（美元）：

  • 马铃薯香料 1 价格 ($) 每公斤：
    [5, 8, 7, 10, 12, 11, 14, 11, 10]

  • 马铃薯香料 2 价格 ($) 每公斤：
    [8, 8, 4, 5, 7, 15, 10, 12, 10]

  • 马铃薯香料 3 价格 ($) 每公斤：
    [4, 7, 5, 6, 10, 9, 11, 15, 11]

什么是一个好的解决方案？

可以通过以下路径生成简单的局部最大值：

  • 第一年：
    [从第一种香料购买 1 公斤（5 美元）]
    [从第三种香料购买 1.25 公斤（5 美元）]
  • 第 2 年：
    [第一种香料出售 1 公斤（8 美元）]
  • 第三年：
    [从第二种香料购买 2 公斤（8 美元）]
  • 第四年：没有
  • 第五年：没有
  • 第六年：没有
  • 第七年：没有
  • 第 8 年：
    [第三种香料销售 1.25 公斤（-15x1.25=18.75 美元）]
    [第二种香料销售 2 公斤（12x2=24 美元）]
  • 9年
    什么都没有

财富 42.75 美元（这是一个例子，肯定不是最大财富）

4

1 回答 1

0

根据您的示例，我假设金钱和土豆是连续数量。这意味着我们在任何给定年份的最大财富价值可以线性分离为每种土豆类型的价值加上现金的价值。

设为一年P(i, k)每 公斤 马铃薯 的 价格. 定义为 1 公斤 马铃薯年的 价值,设 为 1 美元 的 年 价值. 从美元开始的最大财富是。ikV(i, k)ikF(k)kdd * F(0)

作为基本案例，去年k_max我们有：

V(i, k_max) = P(i, k_max)
F(i, k_max) = 1

我们可以通过相互递归计算 和 的剩余值，V如下F所示：

  • 在给定的一年k中，对于每种土豆i，我们可以将土豆保留到下一年，或者以现金出售它们：

    V(i, k) = max(V(i, k+1), P(i, k) * F(k+1))

  • 在给定的一年k中，我们可以购买一些马铃薯i（任何价值i）或持有我们的现金直到下一年：

    F(k) = max(V(i, k+1)/P(i, k), F(k+1))

请注意，由于线性可分性，“混合”策略没有任何好处。在某一年，我们要么将所有现金投资于最赚钱的马铃薯品种，要么根本不投资。同样，对于每种马铃薯类型和年份，我们要么卖掉我们所有的该类型马铃薯，要么将它们保留到下一年。

让我们看看您的示例的结果。下表显示了使用这种方法计算的最优策略。对于每一年，B意味着我们应该把钱投资在那种土豆上，也S意味着我们应该卖掉那种土豆。-意味着我们既不应该购买也不应该出售那一年的那种马铃薯。

    Year 1 2 3 4 5 6 7 8 9
Potato 1 - S - S S S S S S
       2 S S B B B S - S S
       3 B S S S S B B S S

从 10 美元开始，这给了我们：

  • 第 1 年：以 10 美元购买 2.5 公斤马铃薯 3
  • 第 2 年：以 17.50 美元的价格出售 2.5 公斤土豆 3
  • 第 3 年：以 17.50 美元的价格购买 4.375 公斤土豆 2
  • 第 4 年：什么都不做
  • 第 5 年：什么都不做
  • 第 6 年：以 65.625 美元的价格出售 4.375 公斤马铃薯 2
  • 第 7 年：以 65.625 美元的价格购买约 5.97 公斤马铃薯 3
  • 第 8 年：以约 89.49 美元的价格出售约 5.97 公斤马铃薯 3
  • 9年级：什么都不做
于 2021-04-18T22:38:07.777 回答