03
变 治 法
I don' t konw it' s English name
生活的秘密在于。。。用一个烦恼代替另一个烦恼。
——Charles M. Schulz (1922 - 2000)，美国漫画家
变治法，就是基于变换的一种思想方法，首先把问题的实例变得容易求解，然后进行求解。这个方法的思路类似于数学建模的思路，将生活中的问题进行简单的抽象、归化，以便对此进行研究。它不是一种标准的算法，更多的是一种思考的方式。
变治法的工作可以分成两个阶段：首先把问题变得更容易求解，然后对实例进行求解。根据我们对问题实例的变换方式，变治思想有3种主要的类型：
1.实例化简(Instance simplification)。
2.改变表现(Representation Change).
3.问题化简(Problem reduction).
1.实例化简(Instance simplification)。
指将原问题变换为同样问题的一个更简单或者更方便的实例。
预排序是一个这样的栗子：
预排序并不是一种算法设计策略，而是一种意识，在设计算法时要有这种意识，在算法中作预处理，是一种将实例化简的变治策略。
我们在构建数据时就提前进行排序，处理一些问题时就可以非常方便。
例如检验数组元素的唯一性。如果没有预排序，只用蛮力法，需要经过两轮循环，一个个元素检查，时间复杂度为o（n^2）。
而将数组预排序后，相同的元素就会挨着，扫描一遍比较两侧的数据后即可检验元素唯一性，扫描过程的时间复杂度为o（n）。（当然，排序的时间复杂度会更大）
再如模式计算。模式是指一个序列中出现次数最多的一个数值。
同样，如果用蛮力，逐个检查元素出现的次数，需要两遍扫描，复杂度为o（n^2）
预排序将相同的元素紧挨着，通过一遍扫描，累计元素重复出现过的次数，就可知道出现最多的元素。同上，时间复杂度为o（n）。
同理的还有查找问题，这里就不再说了。代码就是排序，也不写了。
2.改变表现(Representation Change).
指将原问题变换为同样实例的不同表现。
我们介绍一个很经典的栗子：霍纳法则。
在计算多项式时，人为计算一般都是一项一项算；然而，当计算机这样计算时，每次求k次方都需要进行多次乘法，效率相当低。
因此，我们将乘法改变为以下形式：
这样，我们只需要进行n次乘法，通过改变了式子（即问题）的表现形式，大大优化了效率。
代码也非常简单，就不写了。（咱们注重思想哈，不是偷懒）
3.问题化简(Problem reduction).
指将原问题变换为另一个问题的实例，这种问题的算法是已知的。（归化思想）转换的难题在于如何找到一个变换的目标算法。
线性规划就是一个很好的目标。我们这里以背包问题为例。
在之前的文章中，我们曾用回溯法解决01背包问题。实际上，背包问题的本质是线性规划。了解了线性规划的本质后，才能更好地解决高维的背包问题。
在高中大家都学过线性规划。线性规划是一种非常好理解的方法，但我们高中的运用大多局限于二维空间。我们将它拓展到n维空间。
在二维空间里，一条的直线Ax+By+C=0能将二维平面分割为两部分。
同样，在三维空间里，Ax+By+Cz+D=0表示一个二维平面，可以将三维空间分割为两个部分。
那么，拓展到n维呢？
一个(n-1)维的分割线，可以将一个n维物体分作两份。
看这样一条分割线：
A0t0+A1t1+A2t2+...+Antn+An+1=0
我们把n个变量看做n个自变量tn，也就是在n维空间里思考。利用一系列约束条件的方程求出可行域，在寻找最优解——一切就变得想高中时一样好理解，自然而然地上升到了n维。哪怕你不清楚n维空间长什么样，在2、3维空间下思考，起码能让问题变得更形象一些。
那么，对于背包问题，我们可以转化为以下不等式组：
其中ni表示第i个物品取几个，vi表示价值，wi表示重量。
0<=w1n1+w2n2+w3n3+...+wnnn<=W
V= v1n1+v2n2+v3n3+...+vnnn
求V的最大值。
（对01背包问题而言，nk只能取0或1.）
背包问题就这样一步步转化为线性规划的问题啦。然而，这个问题也不那么好解决。这里我们就不解决了，等到未来的某天再填上这个坑吧。（相信我们未来还会再遇到背包问题的）
那么，这期的文章就到这儿结束了。
因为一直觉得总结部分很水，所以这次去掉了。。。
感觉这期的代码都和算法本身关系不大？
的确，这次的算法都不是那么的标准。
但依然提供给我们更多看问题的角度，要学会动态地看问题。
那么，赶完这期的我又要继续忙别的去了。。。
考试在即，无力脱身，让我们下次再见~！
