自研Kattis Fridge问题算法是否为贪心算法？相关疑问咨询

问题背景 #

我正在学习Halim等人所著的《Competitive Programming 4》，在「贪心算法」章节中解决了Fridge问题。该问题要求：给定一组数字，找出无法用每个数字至多一次组成的最小正整数。例如：

• 数字串7129045863对应的结果是11
• 数字串55对应的结果是1

我的实现算法 #

digits = list(map(int, input()))

# 统计各数字出现次数
count_0 = 0
digit_count = {1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0}
for digit in digits:
    if digit != 0:
        digit_count[digit] += 1
    else:
        count_0 += 1

# 找到出现次数最少的最小非0数字
min_digit = 1
min_count = digit_count[1]

for digit, cnt in digit_count.items():
    if cnt < min_count:
        min_count = cnt
        min_digit = digit
    if cnt == min_count and digit < min_digit:
        min_digit = digit

# 生成结果
if count_0 + 1 <= min_count:
    result = int("1" + "0"*(count_0+1))
else:
    result = int(str(min_digit) * (min_count+1))

print(result)

算法思路 #

算法核心是针对0的特殊性做处理：

• 先统计所有非0数字的出现次数，单独统计0的数量
• 找到出现次数最少的最小非0数字，计算该数字重复（次数+1）次的数——这是无法用现有数字组成的候选之一
• 计算1后接（0数量+1）个0的数——这是另一类无法组成的候选（因为0的数量不够）
• 在两个候选中取更小的那个，即为答案

核心问题：该算法是否属于贪心算法？ #

答案是属于贪心算法，原因如下：
贪心算法的核心是通过每一步的局部最优选择，最终得到全局最优解。针对这个问题：

• 我们要找的是「无法组成的最小正整数」，而这个数的最优解必然是两类候选中的最小值：要么是某个重复数字组成的数（选出现次数最少的最小数字，确保这个重复数是所有同类型候选里最小的），要么是1后跟多个0的数（唯一的同类型候选）
• 算法直接选择这两类候选中的最小值，本质就是做了局部最优的选择，最终得到全局最优的结果

而你之前尝试的「逐个枚举自然数直到找到无法组成的数」的方法，不属于贪心算法，它是暴力枚举法，效率低下导致超时。贪心算法的优势就在于通过分析问题的最优子结构，直接定位到最优解的特征，无需逐个验证。

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