chapter_greedy/greedy_algorithm/

[giscus[bot]]

chapter_greedy/greedy_algorithm/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_greedy/greedy_algorithm/

[GuanshiyinPusa]

能把最后几个典型问题再写写吗？Dijkstra 现在大二大三都在学和用的

[krahets]

好的，已加入任务队列

[WhiteRhinos]

 /**
     * 根据key-value创建huffman编码树
     * 和之前的一样不过加入的data
     *
     * @param counter 节点信息
     */
    public void createCodingTree(HashMap<Byte, Integer> counter)
    {
        // 管理节点
        ArrayList<HuffmanNode> huffmanNodes = new ArrayList<>();
        // 创建节点
        for (Byte key : counter.keySet())
        {
            huffmanNodes.add(new HuffmanNode(key, counter.get(key)));
        }

        // 最后会剩下一个根节点
        while (huffmanNodes.size() > 1)
        {
            // 1.按照权值对节点排序
            huffmanNodes.sort(new Comparator<HuffmanNode>()
            {
                @Override
                public int compare(HuffmanNode o1, HuffmanNode o2)
                {
                    return o1.weight - o2.weight;
                }
            });

            // 2.构建二叉树
            // 2.1.获取权值最小的两个节点
            HuffmanNode first = huffmanNodes.get(0);
            HuffmanNode second = huffmanNodes.get(1);
            // 2.2.创建父节点
            HuffmanNode parent = new HuffmanNode(first.weight + second.weight);
            // 2.3.构建二叉树
            parent.left = first;
            parent.right = second;

            // 3.删除两个节点并将父节点加入
            huffmanNodes.remove(0);
            huffmanNodes.remove(0);
            huffmanNodes.add(parent);
        }

        this.root = huffmanNodes.get(0);
    }

[krahets]

谢谢分享，但完整代码实在是太长啦，建议可以把代码写到博客里，并分享一个链接

[WhiteRhinos]

ok

[mxdmm123]

大家好呀

[silde1]

可以加一些有关贪心问题的证明吗，这真的令人很头疼

[krahets]

贪心的确比较难，可以多做做题～

[anxiaochou]

硬币那个也可以整除实现吧

[krahets]

确实，整除 + 余数的方法在数据较大时下会更快

[sakurakugu]

时间复杂度为 $O( \frac{amt}{\min(coins)} )$ 。这比动态规划解法的时间复杂度 $O(n \times amt)$ 提升了一个数量级。

上面的“提升了一个数量级”应该是“降低了一个数量级”吧

[anxiaochou]

意思应该是优化了一个数量级

[krahets]

谢谢指正！

[heyach]

有一个小疑问，贪心策略是每次选取最接近目标金额的硬币，要达成这样的操作步骤，需要coins是有序的吧
coinChangeGreedy([1, 49, 50], 98) = 49
coinChangeGreedy([1, 50, 49], 98) = 2
题目中并没有提coins是面值有序的

[anxiaochou]

你看代码里，它假设列表是有序的

[SydCS]

用贪心解零钱兑换是不是存在问题？
例如，假设有硬币面额为1,3,4，目标金额为6。按照贪心算法，如果先选择最大的硬币4，再选择两个1，总共需要3枚硬币。但实际上，最优解是两个3面额的硬币，只需要2枚硬币。

[krahets]

是的，文中已经说明：对于零钱兑换问题，贪心算法无法保证找到全局最优解，并且有可能找到非常差的解。它更适合用动态规划解决。

[syutengu]

想接此话题请教作者一个可能与算法无关的问题：
如果一个算法只能解决部分特定数据下的问题，而无法在任何数据下获得最优解。那么这种“局限解”有什么实际意义？（能够理解作者接上一章继续使用“零钱兑换”例子，但不知道为什么作者不直接用一个能通过贪心算法彻底解决问题的更好例子，假设这样的更好例子的确存在。）
可不可以认为至少对于“零钱兑换”问题，贪心算法是完全不重要的，不值得一提的？

[LeoY2020]

无法适配LaTeX

[Danbor86]

正例 ：在该硬币组合下，给定任意 ，贪心算法都可以找到最优解。

挺好奇人民币也正巧是这些面额的纸币是不是和这个有关系，就是令人找零/凑钱的时候永远可以从大额到小额一次考虑。

[krahets]

没错（可以尝试去掉某些面值，我们就会发现贪心算法在某些金额下不能找到最优解了）

[480284856]

老学究用 $O(n^3)$ 的算法，我想能不能这样：先用DP算法求解一遍，再用贪心算法求解一遍，如果两者结果相同，那么就说明，这样的硬币序列可以用贪心算法来解决。这样，时间复杂度应该是更低的哈哈哈。也就是说，如果一个硬币序列满足这样的条件：使用两种算法求解的结果一样，那么说明这种硬币序列可以用贪心算法来求解。

图一乐，莫喷哈哈。

[JinZhihaoChina]

k神请问贪心算法再解决最小里程数时我应该如何的优化代码量呢是Python哦

[liweijian199011]

想问一下，最后这四种算法，分治，回溯，动态，贪心这么排版有什么特殊的想法吗？以前我记得都先学贪心的。这四种算法的学习顺序有没有什么讲究？

[pianfan]

一般都先学分治和回溯吧，然后学贪心最后学动态规划，难度有逐步递增的意思。但实际上贪心比动态规划上限更高。

[jackzjw]

运行零钱兑换的代码，有些测试用例通不过，有人遇到嘛？