有趣的算法问题之真的有趣吗
本文由在当地较为英俊的男子金天大神原创，版权所有，欢迎转载，本文首发地址 https://jinfagang.github.io 。但请保留这段版权信息，多谢合作，有任何疑问欢迎通过微信联系我交流：
jintianiloveu
继续上一个继续说。说完了动态规划最优代表性的问题，该研究点其他的吧。贪心算法？
贪心算法
感觉贪心算法适合处理序列决策问题，也即是没有固定章法的问题，这个时候一个牛逼的题目出现在了你的面前：
移动纸牌问题
假设有N堆纸牌，你现在需要在相邻的每两堆之间相互移动，使得最后每堆的数目相同，当然，纸牌的总数是N的倍数的，请问这样最少的移动次数是多少次？
哇，好厉害的题目。其实也很简单，贪心算法其实得到的并不一定是最优的解法，你只需要实现它，既可以，你要证明它是最优，对不起，很难证明，只要你能够解决就是牛逼的。
这个问题很好理解，我们假设有4堆排，分别为：9, 8, 17, 6, 很显然我们可以知道最终的平均值为10，我们归一化一下，全部剪掉10：
- -1, -2, 7, -4, 我们现在从第一个数开始，与后面的数相加；
- 0, -3, 7, -4,
- 0， 0，4, -4;
- 0, 0, 0, 0; 经过3次移动，最终变味了0.
代码就不写了，比较简单。
再来一个题目：
背包问题
背包问题其实也可以说是动态规划吧。我形象的描述一下背包问题：
我们要求的是这么一个值F(W, N)，也就是在给定W和N的情况下求这个值。
我们这样思考，加入W或者N为0，那么肯定这个值也是0，因为没有背包或者没有物品都是没有价值的。如果都不为0我们思考两种情况：
- 如果不把最后一个物品放入背包，此时能够实现的最大价值为F(W, N-1);
- 这个时候最后一个物品有两个选择，要么放要么不放，假如放，那么放入之后的价值应该是F(W - Wn, N) + Vn，这个就是等于假如没有最后一个体积背包的情况下的最大值加上这最后一个物品，同时假如说不放，那么价值应该是或者说等于，没有这个物品，背包减少Wn时候的最大值，即F(W-Wn, N-1),综合两种情况就是 max{F(W - Wn, N) + Vn, F(W-Wn, N-1)}
上面的思路放到程序实现可以这样：
new -> F[W][N], V[N], W[N]
F[0][N] = 0;
F[W][0] = 0;
if V[N] > W, F[W][N] = F[W][N-1];
if V[N] <= W, F[W][N] = max{F[W][N-1], F[W-W[N]][N-1] + V[N]}
程序就不写了，有了这个思路，实现起来也是极其简单的。真正重要的是这个递归的思想。
