找零问题的贪心算法何时总是最优、何时必然失效？

首先你提到的正则（Canonical）硬币体系，就是指对任意找零金额，贪心算法都能输出最少硬币数最优解的面额体系，相关判定规则和失效特征如下：

贪心算法始终适用的面额特征 #

• 基础必要前提：面额严格递增，且最小面额为1（如果最小面额大于1，会存在部分金额无法找零，不满足通用找零的基础要求）
• 常用的充分非必要判断规则：每一个面额的取值，都大于等于比它小的相邻面额的2倍。比如美国美分体系[1,5,10,25]，5≥12、10≥52、25≥10*2，符合该规则，贪心永远有效
• 严谨的全局判定方法：对于面额集合c[0]=1 < c[1] < c[2] < ... < c[n-1]，只需要验证所有小于c[n-2] + c[n-1]的金额下，贪心解都等于最优解，就能证明该体系是全局正则的，不需要验证无穷多的金额，该结论已被学术研究证明。

贪心算法必然失效的面额特征 #

核心失效逻辑：存在某一金额，用多个小面额组合的硬币总数，少于贪心优先选大面额得到的硬币总数。符合以下任意一种特征的面额体系，大概率会出现贪心失效的情况：

• 面额之间不存在整除关系，且存在多个小面额之和等于某一金额、硬币数比贪心组合更少：经典反例如面额[1,3,4]，找零6元时贪心会给出4+1+1共3枚硬币，但最优解是3+3共2枚，贪心直接失效
• 面额增长不符合最小倍乘要求：比如面额[1,5,8]，找零10元时贪心给出8+1+1共3枚，最优解是5+5共2枚
• 存在连续多个小面额之和大于相邻大面额，但总硬币数更少：这是最直观的失效信号，只要出现这种情况，对应的总金额就是贪心失效的反例。

内容的提问来源于stack exchange，提问作者King