国际货币投机问题算法国际货币投机问题每天货币的汇率是不断变化的,例如某天的汇率是：1美元能兑换0.7英镑,1英镑又能兑换9.5法国法郎,而1法国法郎能兑换0.16美国美元,那么投机商人分析

Question

国际货币投机问题算法
国际货币投机问题
每天货币的汇率是不断变化的,例如某天的汇率是：1美元能兑换0.7英镑,1英镑又能兑换9.5法国法郎,而1法国法郎能兑换0.16美国美元,那么投机商人分析发现,经过一连串的兑换后能够有一定的利润可图.例如初始拿着1美元进行一轮兑换后得到1×0.7×9.5×0.16=1.064美元,因而能得到6.4%的利润.
要求：编写程序求解一个能够有利润可图的兑换序列,可以从任何货币作为开始,但是要求兑换过程起点与终点应当是同一种货币,如上例从美元开始兑换,经过一轮兑换后最后换成美元.
输入：
输入的是一个矩阵,这个矩阵的维数就是国家的数目,每行代表每个国家的汇率值,每列代表第i列国家与其它国家货币的兑换汇率值,因而矩阵中的对角线元素都是1（自己与自己兑换的原因）,故省略掉对角线元素,矩阵的最大维数是20,最小是2.例如：第一列表示第一个国家与其它国家（2

Answer 1

我觉得这个问题是这样的：
首先复原输入矩阵trans[][]
然后设矩阵a[i][j][k]表示从state i 出发,经过j步,到达k的最大值
有a[i][j][k] = max_{t}(a[i][j-1][t]*trans[t][k])
至于无解的判断,应该是计算到j=n+1为止,因为
假设n=4,有解（不一定最优解）1,2,3,4,3,4,1,则或者1,2,3,1是解（3,4,3赔钱）,或者3,4,3是解（3,4,3赚钱）
欢迎讨论