1. 局部选择需要全局理由
贪心每次作出一个选择,不枚举所有后续组合。能否正确,关键是证明某个最优解可以包含这次选择,然后在剩余问题重复该论证。几个样例通过不是证明。
动态规划保存多个状态的最优结果,贪心只沿一个策略推进;它们不按问题维度区分,也不能说动态规划天然有“回退功能”。先找反例,再尝试交换论证。
2. 活动安排:最早结束
输入为有限数值端点的活动区间 [start, end),要求 start < end;端点相接可以同时选择。目标是最多安排多少活动,不是覆盖某一整段时间,也不是最大总收益。
把任何最优方案的第一项替换为结束最早的活动,不会减少后面可用的时间,所以总活动数不会更差。剩余活动重复这个交换论证。
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. 分配饼干:最小够用即可
孩子需求与饼干大小均为非负有限数值,一块饼干最多给一个孩子,每个孩子最多一块。先排序,给需求最小的孩子分配能满足他的最小饼干;更大的饼干留给后面不会更差。小到无法满足当前最小需求的饼干,也不能满足任何后续需求,可直接跳过。
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. 分数背包:只有能切分时才按密度选
物品每件最多使用一次,但允许任意切分。重量为正、价值非负、容量非负,均为有限数值且计算结果有限。单位重量价值越高越先选;若低密度物品占了容量而高密度还没用完,可以交换同重量部分提高价值,因此按密度选择成立。
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。小活动集合用枚举最优值对照,测试乱序、端点相接和空输入;分数背包测试容量不足与零价值。
为每种策略写一句交换理由,再改变一个条件寻找反例。若只能说“看起来更优”,就还没有完成正确性说明。
评论
正在加载评论…