本来想打电话问你的，不过明天我有考试，你说你看见了就简单得作答一下子呗
oh....
first fit is 2-approximate...to show that,
We first show that all bins (最多1个例外) at the end will be at least half full
Say each bin has capacity P
The intuition is that, at each instance in the packing process, if there's already a less-than-half full bin, the next item will either
1. settle in a new empty bin, if it's weight > P/2, or
2. settle in that less-than-half full bin
Either case, # of less-than-half full bins remains at most one....you can continue the proof...
For the second part, I dunno how to attack it...will try if i get more time
We first show that all bins (最多1个例外) at the end will be at least half full
Say each bin has capacity P
The intuition is that, at each instance in the packing process, if there's already a less-than-half full bin, the next item will either
1. settle in a new empty bin, if it's weight > P/2, or
2. settle in that less-than-half full bin
Either case, # of less-than-half full bins remains at most one....you can continue the proof...
For the second part, I dunno how to attack it...will try if i get more time
Huasing Association 1999 - 2013