贪心算法

算法教程 · 第 7 章 · 7 次浏览

贪心：每一步选当前最优，期望全局最优（能用时效率最高，但要证明局部最优=全局最优）。回溯：穷举所有可能，走不通就回头（组合、排列、棋盘问题）。

贪心经典

找零钱（某些币值）、区间调度、霍夫曼编码。贪心不保证正确，适合有"贪心性质"的问题。

回溯模板

选择 → 递归 → 撤销选择。全排列、子集、N 皇后都是回溯。

代码示例

# 贪心：活动安排（结束早优先）
def max_activities(activities):
    activities.sort(key=lambda x: x[1])   # 按结束时间排序
    count, end = 0, -1
    for start, finish in activities:
        if start >= end:                  # 不冲突就选
            count += 1
            end = finish
    return count

print(max_activities([(1, 3), (2, 5), (3, 6), (5, 8)]))   # 2

# 回溯：全排列
def permute(nums):
    res = []
    def backtrack(path, remaining):
        if not remaining:
            res.append(path[:])
            return
        for i in range(len(remaining)):
            backtrack(path + [remaining[i]],
                      remaining[:i] + remaining[i + 1:])
    backtrack([], nums)
    return res

print(permute([1, 2, 3]))   # 6 种排列

📚 Python 语法速查

常用条目速查，完整版见对应教程章节。可复制代码到在线运行中测试。

写法 / 语法	作用
`print("hello")`	输出到控制台
`name = "张三"`	变量赋值（无需声明类型）
`if x > 0: ...`	条件判断（注意冒号和缩进）
`for i in range(10): ...`	循环（缩进是语法的一部分）
`while x < 10: ...`	条件循环
`def fn(a, b): return a + b`	定义函数
`class Person: ...`	定义类
`list = [1, 2, 3]`	列表（可改）
`tuple = (1, 2)`	元组（不可改）
`dict = {"key": "value"}`	字典（键值对）
`set = {1, 2, 3}`	集合（去重）
`len(obj)`	取长度
`str(x) / int(x) / float(x)`	类型转换
`s.split(",")`	字符串按分隔符拆分
`" ".join(list)`	列表拼接成字符串
`import os`	导入模块
`from math import sqrt`	从模块导入指定函数
`try: ... except Exception as e: ...`	异常捕获
`with open("a.txt", "r") as f: ...`	文件读取（自动关闭）
`f"你好 {name}"`	f-string 格式化
`lambda x: x * 2`	匿名函数
`list(map(fn, arr))`	函数式处理列表
`range(start, stop, step)`	生成数字序列
`if __name__ == "__main__":`	主入口判断
`pip install 包名`	安装第三方包（命令行）