玩家分析倩女幽魂最短时间跑商方法
这篇文章写出来不是给一般玩家看的，所以看不懂也好，觉得幼稚、苛刻也好，请轻喷。
相信各位会跑的人都明白，跑商无非两种情况：一种是最短时间完成15W，另一种是商票内金额最大。
对于第二种情况，通过放缩法，将启动资金调成14W，这样只要通过最小差值来补齐数值，最后压19个玉石，在绝对最高的1W6卖出，这时就会得到理论最大值为45W。
然而每周真正能达到这个理论最大值的人，少之又少，大多数人追求的其实是第一种情况——最短时间跑到15W。
不过这样写出来，思路会有点散，于是我们重申一下问题好了：
杭州金陵阿格拉荒漠和仙山五个地方，每个地方都有2个商人。每个地方2个商人出售的货物相同，但有些许价格差异。每样物品都可以在每个地方卖。
从杭州出发，到每个地点的距离可知。
背包上限19个物品，资金到达15W时必需空票回到杭州才算完成任务。
解释：
由于商人-商人，城市-城市之间距离可测，所以我们可以用T值数组的形式给出。不过这个数组是个二位数组，第一维度是起点，第二维度是终点。有些时候，起点-终点之间的数值是不一样的。比如说杭州-阿格拉需要跑，但是阿格拉到杭州可以传送。
之后，我们可以用卖出价格表数组W来表示每个地方卖出的货物价格。这个不多解释了。于此同时，还需要一个权重数组来表示权重，设置每种货物权重都为1，因为占据1个包裹位置。
对于买入价格，虽然每个地点买入的价格只有6个，但我接下来的算法中需要一些特殊的设置，所以我们多一个名叫“金币”的货物。他的买入卖出价为1，权重为0.
这样就可以把问题简化成，每个地方-每个地方用所有的钱取“价值最大的背包组合”来处理一条路上一次的跑商。
由于对应跑商地点，每个地点排列组合有20种选择，这时，通过状态数组来记录当前20种选择对应背包盈利情况。背包盈利情况为：
for i=1..N
for v=0..V f[v]=max
{f[v],f[v-c[i]]+w[i]}
C数组对应的最大限度是19，w则通过两地取差值可以得出单维度的数组。
但对于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跑商迷宫就可以得到正确的时间了。
