逻辑学君已阵亡 看不懂的倩女跑商神理论

　　但对于dp思想中，有这样一句至理名言“选择有后效性”，如果单纯的通过每一次的规划单维度的完全背包，假设杭州到荒漠的盈利价值最高，现实中就变成了“杭州-荒漠，杭州-荒漠”

　　众所周知的是，荒漠不是杭州，因此之间的时间是不能叠加的，如果叠加则需要计算“荒漠-阿格拉-杭州”中间的时间。因此体现这个后效性，必须添加第三个维度对应当前位置。

　　这里解释下dp后的贪心算法：

　　⒈建立数学模型来描述问题。

　　⒉把求解的问题分成若干个子问题。

　　⒊对每一子问题求解，得到子问题的局部最优解。

　　⒋把子问题的解局部最优解合成原来解问题的一个解。

　　我们做的时候，每一次跑商盈利最大实际上就是一次贪心，局部最优所以整体最优，但每一次由于都有后效性，所以我们把每一次作为一层，每一层都保存在三维数组中进行层搜。

　　因此，我们虚拟设置每个地方都能买入每件商品，但是每个地方买入其他地方物品的价格等于对应卖出价格。

　　这里先举例说明：

　　如果仙山商人的卖出玉石价格为9000，则仙山设置玉石商人买入玉石的价格为9000.这时候，买入和卖出的价格相同，所以获利为0，在贪心计算的时候，即使是仙山货商那里，由于不获利，所以不符合贪心求局部最大的原则，不会买入其他地方买入的货物。

　　这时，解决了局部层搜的问题，还需要处理时间对应T数组

　　但这时就有一个严重的问题：并不是每个地方都能买入每件商品，比如昆仑荒漠不能买入茶叶。这不符合层搜的要求。

　　这样的设置，代表了单次的跑商，买入了全部，也卖出了全部，这时候一次交易就不会出现后效性问题。这样的处理是为了解决“卖出一部分”的情况，也就是说，相当于你卖出了一部分，然而买入了一定的商品再去下个地方卖出的情况，比如：

　　杭州买入19个藕粉，荒漠卖了9个换了3个马匹再去阿格拉卖了6个藕粉……这样的情况。

　　那么，最终结果用f数组来搜，f[i][j][k]=Min{ f[i][j][k]， f[i-1][j0][k0]+t[j][j0]}

　　这时候的循环，则反向循环，因为我们求的是最小，而不是价值最大，是完全背包问题的一种变型。

　　但涉及3个维度，这个公式并没有进行演算，且这个数组也是在价格固定情况下做层搜处理的。

　　OK，到此为止，上面的部分属于基础的准备内容，个人感觉里面确实有问题，但没发现问题在那里，感觉上一次NPC一次贪心解决问题有点小看这个题目，不过暂时没想出别的方法。接下来要结合现实问题来分析了。

　　我们知道倩女价格实际上是基础价格加随机函数加概率模型的形式决定的，比如藕粉买入价是2800+随机数(-200，+200)+暴击概率。

　　所谓的暴击概率指的是帮会频道提示的“藕粉可以治疗禽流感”这种不能放弃治疗的句子。

　　因此寻找最佳路径的时候，忽略掉暴击概率和随机数区间得到上述公式，而加上概率时，实际上需要计算概率大小，因此我们需要给f数组增加第四个维度。

　　这个第四个维度意义是对应概率点时间得到的跑商总时间长度。这需要对概率进行层搜。不过蛋疼的浮点型需要转化成整数型里做，因此，计算概率的时候会超出时间复杂度。因此，计算的时候需要先对概率进行层搜简化函数。

　　忘记说了一个前提，跑商迷宫的时间计算和跑商从帮会出来以及过图时间。跑商迷宫每次跑商都需要经历一次，跑商过图计算在T函数中了，所以只要将最后的F数组求最小，然后Fmin+t跑商迷宫就可以得到正确的时间了。

　　最后解释下，这个问题和数学无关，是算法设计、策略论相关的，不过做的时候还需要一点数据结构的知识。

　　我数学很差……

　　小编注：有没有童鞋看完整篇分析还能看懂的，快站出来，给各位算法学经济学数学学霸给跪了!