随着时间的推移，通过销售和购买土豆香料来获得最大的财富

Question

说，我们最初的财富是10美元，我们想通过购买和销售土豆来赚钱，并且以一种神奇的方式知道每种马铃薯香料每年每公斤的价格($)。寻找最终最大财富或局部最大财富的最佳算法是什么？

!！如果你有15美元的财富，而你在一年中卖出了一些公斤，并且赚了4美元，你就不能在同一年买到19美元的东西，他们是独立的，所以你应该有钱去买东西，然后才能在同一年卖出其他东西!!！

e.g

起始财富: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公斤(8美元)的第一香料

• 第三年：

购买2公斤(8美元)从第二个香料

• 第四年:无

• 第5年:无物

• 第6年:无物

• 第7年:无物

H 137第8年：

销售1.25kg (-15x1.25=18.75美元)从第三香料

• 第9年

nothing

财富42.75美元(这是一个例子，当然不是最大财富)

Answer 1

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

假设P(i, k)是k年的每公斤土豆i的价格。将V(i, k)定义为k中1公斤土豆i的价值，而F(k)定义为k年中1美元的价值。从d美元开始的最大财富是d * 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(10
• )第2年:以17.50美元
• 第3年出售2.5公斤马铃薯2，价格为17.50美元
• 年4:不做任何事<代码>H 142第5年:不做任何事情<代码>H 243<代码>H 144第6年:以65.625美元出售4.375公斤<代码>H 245<代码>H 146第7年:以65.625美元<代码>H 247/代码><代码>H 148 8:出售马铃薯3 ~5.97公斤~$89.49
• 9: nothing