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