你是请教新生，还是混充新生请教？

你是请教新生，还是混充新生请教？

approximation algorithmThis bin-pack problem is extensively used as an example for approximation algorithms in NP-complete problems. You should be able to find the explainations and proofs (for both FF and FFD) in a reasonable college computer algorithm textbook, under NP-complete section, but it might not be covered in an undergraduate algorithm course. Briefly put, given an optimal solution of value O to an NP problem, and an approximation algorithm (in polynomial time) that outputs a solution that is k*O on average, then this approximation algorithm is called a k-approximation. If I remember correctly, FFD is an 3/2 approximation algorithm.

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