Skip to content

1. 局部选择需要全局理由 ​

贪心每次作出一个选择,不枚举所有后续组合。能否正确,关键是证明某个最优解可以包含这次选择,然后在剩余问题重复该论证。几个样例通过不是证明。

动态规划保存多个状态的最优结果,贪心只沿一个策略推进;它们不按问题维度区分,也不能说动态规划天然有“回退功能”。先找反例,再尝试交换论证。

2. 活动安排:最早结束 ​

输入为有限数值端点的活动区间 [start, end),要求 start < end;端点相接可以同时选择。目标是最多安排多少活动,不是覆盖某一整段时间,也不是最大总收益。

把任何最优方案的第一项替换为结束最早的活动,不会减少后面可用的时间,所以总活动数不会更差。剩余活动重复这个交换论证。

js
function maxActivities(intervals) {
    const sorted = intervals.slice().sort((a, b) => a[1] - b[1]);
    let end = -Infinity;
    let count = 0;
    for (const interval of sorted) {
        if (interval[0] >= end) {
            end = interval[1];
            count++;
        }
    }
    return count;
}

不修改输入。常用比较排序模型下时间为 O(n log n),复制数组需 O(n) 空间,排序内部空间取决于实现。空数组返回零。按最早开始会误选 [0,10] 而排除 [1,2]、[2,3];若每项有不同收益,最早结束也不一定最优。

3. 分配饼干:最小够用即可 ​

孩子需求与饼干大小均为非负有限数值,一块饼干最多给一个孩子,每个孩子最多一块。先排序,给需求最小的孩子分配能满足他的最小饼干;更大的饼干留给后面不会更差。小到无法满足当前最小需求的饼干,也不能满足任何后续需求,可直接跳过。

js
function findContentChildren(greed, sizes) {
    const children = greed.slice().sort((a, b) => a - b);
    const cookies = sizes.slice().sort((a, b) => a - b);
    let child = 0;
    for (const size of cookies) {
        if (child < children.length && size >= children[child]) child++;
    }
    return child;
}

时间为 O(n log n + m log m),复制存储为 O(n + m),不修改输入。不是相邻评分分糖果题,不要混用两种模型。

4. 分数背包:只有能切分时才按密度选 ​

物品每件最多使用一次,但允许任意切分。重量为正、价值非负、容量非负,均为有限数值且计算结果有限。单位重量价值越高越先选;若低密度物品占了容量而高密度还没用完,可以交换同重量部分提高价值,因此按密度选择成立。

js
function fractionalKnapsack(items, capacity) {
    const sorted = items.slice().sort((a, b) => b.value / b.weight - a.value / a.weight);
    let remaining = capacity;
    let total = 0;
    for (const item of sorted) {
        const weight = Math.min(remaining, item.weight);
        total += weight / item.weight * item.value;
        remaining -= weight;
        if (remaining === 0) break;
    }
    return total;
}

时间为 O(n log n),复制空间为 O(n);返回数值可能有浮点误差,测试使用容差。密度计算也需在有限数值范围内。它不是零一背包,更不是每件无限重复。

零一反例:重量 [10,20,30]、价值 [60,100,120]、容量 50。按密度拿前两件只得 160,选后两件得到 220;可切分时则能得到 240。不可切分版本见背包专题。

5. 找零与其他保留主题 ​

优先最大面额不对任意币制成立:面额 [1,3,4] 组成 6,贪心得 4+1+1,而 3+3 更少。不能因某套常用硬币可行就推广;一般币制使用完全背包求最少数量。

任务调度与教师排课先明确资源、收益、截止时间和冲突规则:单会场最多活动可复用本篇,带权收益、多教室或课程先修是不同问题,需要重新建模。

霍夫曼编码保留为堆的进阶应用:每次合并两个最小频率节点,将总频率放回优先队列,直到剩一个节点。给左右边标记零/一,根到叶路径形成前缀编码;解码遇到叶子就输出并回到根,不是“尽量读取最长可解码串”。至少两个符号时,最小频率符号可交换到最深兄弟叶而不增加加权路径长度,再归约为合并问题。单符号输入需另定编码约定。压缩效果取决于分布和编码表成本,没有固定压缩率保证。

6. 验证与闭卷练习 ​

运行 node --test tests/algorithm-strategies-examples.test.mjs。小活动集合用枚举最优值对照,测试乱序、端点相接和空输入;分数背包测试容量不足与零价值。

为每种策略写一句交换理由,再改变一个条件寻找反例。若只能说“看起来更优”,就还没有完成正确性说明。

评论

正在加载评论…