标签:交换论证
7 个条目
-
概念 反悔贪心
先维护一个可行解,用堆、链表或残余结构保存反悔项;出现更优交换时替换旧选择,正确性由交换论证保证。
2026-11-17 -
概念 贪心选择模型
选择型贪心的集合模型:按代价非减序加入可行元素;安全选择与交换论证给出正确性条件,拟阵是充分条件。
2026-11-17 -
题目 区间调度
选择最多两两不相交的区间;按右端点升序,能选就选,交换论证给出最优性。
2026-11-17 -
题目 国王游戏
重排大臣顺序,最小化最大奖励;按左右手数字乘积升序排序,高精度计算。
2026-11-17 -
概念 贪心决策模型
把贪心抽象为确定性序贯决策:状态、动作、代价与安全选择;选择型和合并型都落入同一框架。
2026-11-15 -
概念 贪心合并模型
反复合并两个最小权对象,代价为两权之和;用二叉合并树与交换论证证明最优,是 Huffman 合并的抽象。
2026-11-15 -
概念 序贪心条件
在可用集合上按优先级取极值;静态全序对应排序贪心,后继关系对应最佳优先与多路归并。
2026-11-15