First Fit Decreasing

The tight bound of first fit decreasing bin-packing algorithm is

zgc 是神

---

已知对于任意 , 满足

同时已知，决定两个盒子是否足够存下当前这组物品 是 问题

证明: , 并且除非 , 否则 是最好的近似比例

证明：

对于 , 有 成立

对于 , 总是成立

对于 , 那么

由于 是整数，所以 , 成立

接下来证明是最佳比例

如果存在 , 那么如果 , 那么 , 所以 , 这回答了上面的 问题，即不能用两个盒子存下

如果 , 那么 , 所以, 这回答了上面的 问题，即能用两个盒子存下

所以 问题被我们用多项式时间解决了，所以

所以如果假设 , 就不存在更好的比例