题意概括:买一定数量的灯泡,通过将低电压灯泡可以替换为高电压灯泡来节省成本,反过来不行,每种电压的电源可以带动无数个该电压的灯泡
需要注意的是,每种电压的灯泡都可以有多种替换方案(包括“不替换“)来节省成本
- 排除“部分替换”,“间接替换”,“嵌套替换”方案
- 剩下一些需要具体计算的“次优方案”
- 最后比较“次有方案”得出全局相关的唯一“最优方案”
理解并排除以下三种非次优方案(可以证明一定不是最优方案的候选)非常关键:
- 不存在“部分替换”:每种灯泡的替换方式只有“全部替换”和“不替换”两种,但不可能“部分替换”
- 不存在“间接替换”:若一种灯泡作为被替换的目标,则它不再可能再替换为别的灯泡,相当于该种灯泡不替换
- 不存在“嵌套替换”:存在多种灯泡时,若低电压灯泡替换到高号灯泡,且中电压灯泡作为被替换到的目标或不替换(可以看作是一种“自替换”),则该方案一定不是最优方案,直接排除
我们接下来分别证明这三条结论。
排除“部分替换” #
不可能部分替换这一点非常好证明
现有两种电压的灯泡
序号 | 电压 | 电源价格 | 灯泡单价 | 所需数量 |
---|---|---|---|---|
1 | 低 | K1 | C1 | L1 |
2 | 高 | K2 | C2 | L2 |
当 C1 >= C2 时,1号灯泡全部替换为2号灯泡明显优于部分替换(无论替换多少个),全部替换至少可以省下 K1 电源钱
当 C1 < C2 时,将1号灯泡部分替换2号灯泡,只是在徒增成本。此时该采用哪种方案的关键,就是判断 因灯泡单价上涨而所需的钱 是否大于 买电源的钱
- 当 (C2 - C1) * L1 > C1 * L1 + K1 时,也就是替换灯泡多出来的钱,比买1号灯泡的电源还多,则选择“不替换“
- 反之,选择“全部替换”,虽然灯泡单价更高,但通过不买1号灯泡的电源来省钱
得出结论一:每种灯泡的替换方式只有“全部替换”和“不替换”两种,但不可能“部分替换”

从此节之后,将不再讨论“部分替换”,如提到替换,必然是“全部替换”。
排除”间接替换“ #
序号 | 电压 | 电源价格 | 灯泡单价 | 所需数量 |
---|---|---|---|---|
1 | 低 | K1 | C1 | L1 |
2 | 中 | K2 | C2 | L2 |
3 | 高 | K3 | C3 | L3 |
对于上面三种灯泡,存在这样的次优替换方案:1号 替换为 2号 , 2号 替换为 3号
...