01 | 硬币找零问题：从贪心算法说起

重新调整得了java代码部分，提高代码的可读性 private static void getMinCoinCountOfValue() { // 硬币面值 int[] values = {5, 3}; // 总价 int total = 11; int minCoinCount = getMinCoinCountOfValueHelper(total, values); // 输出结果 System.out.println(minCoinCount); } /** * @param total 金额 * @param coins 币种数组，从大到小排序 * @return 返回币数，如果返回-1表示无法凑够total */ private static int getMinCoinCountOfValueHelper(int total, int[] coins) { if (coins.length == 0) { return -1; } //当前币值 int currentCoin = coins[0]; //使用当前币值数量 int useCurrentCoinCount = total / currentCoin; int restTotal = total - useCurrentCoinCount * currentCoin; // 如果restTotal为0，表示余额已除尽，组合完成 if (restTotal == 0) { return useCurrentCoinCount; } // 其他币种数量 int coninCount = -1; // 剩余的币种 int[] restCoins = Arrays.copyOfRange(coins, 1, coins.length); while (useCurrentCoinCount >= 0) { // 否则尝试用剩余面值求当前余额的硬币总数 coninCount = getMinCoinCountOfValueHelper(restTotal, restCoins); // 如果后续没有有可用组合,退一步，当前useCurrentCoinCount币数减1 if (coninCount == -1) { // 否则尝试把当前面值数-1 useCurrentCoinCount--; // 重新计算restTotal restTotal = total - useCurrentCoinCount * currentCoin; } else { return useCurrentCoinCount + coninCount; } } return -1; }

上述回溯+贪心并不能取到最优解, 比如[1,7,10] amount=14 那么根据递归深搜 10 + 1 + 1 + 1 + 1 会比 7 + 7 先到

老师说的很生动！用递归加局部最优的方法一定能得到正解。但是如果问题变得更加复杂的情况下，例如我们有1亿中硬币可以用，总币值为几万亿。可能还需要优化一下算法性能或者用分布式计算把性能提高？ 这让我想到了ai中的reinforcement learning。个人认为有些偏全局优化？就如alphaGo，每一步棋都需要以整个棋局为出发点考虑。有点像老师这个算法里面的递归，即每尝试走一步的时候都会记录状态，用树状结构罗列所有可能性然后回溯。通过神经网络来的weight值估算是不是应该回溯。另外即使找到最优解了，还可以设置exploit更多最优的可能。纯个人理解，有点发散，希望老师指正！

递归的目的是求解 回溯+递归的目的是枚举所有组合的解，并取最优解返回 没有回溯，递归只能获得一个解或者无解，获得的解不一定是最优解 递归是一种算法结构，回溯是一种算法思想 一般回溯多用递归实现

老师，第一段代码的第22行，是不是应该为调用GetMinCoinCountHelper?

测试在原有贪心基础上加上回溯可以找到一组可行解： int[] values = new int[] {5, 3}; // 硬币面值 int total = 11; // 总价 贪心策略求出可行解不是全局最优解： values = new int[]{5, 4, 1}; // 硬币面值 total = 13; // 总价

对动规有了新的了解，感谢老师！

GetMinCoinCountLoop这个方法是在干嘛呀？感觉直接getMinCoinCountOfValue(total, values, 0)不就行了吗？GetMinCoinCountLoop将数组元素换来换去有啥意义吗？有点看不懂，要是多加点注释就好了

看来半天回溯+贪心，发现其实就是把所有情况都枚举出来取最小值。。。。。。

时隔1个多月，二刷一下，发现这一篇比第二篇代码难读，就在于变量和函数的命名，实在是又长，意义又差，比如valueCount 完全不如valuelength这样的名字来的直观，而且取名还很像，很多时候看了几行，就忘记标识符号的意思是啥来着了，第二篇命名改进了之后可读性就好很多。