请教一个算法的问题一个junior问我一个算法的问题，可是我的算法是用英文学的，看不懂他的题干。哪位曾经用中文学过算法的朋友帮个忙吧。谢谢~~
请考虑装箱问题的贪婪算法，他也被称为优先容纳算法（first-fit,FF）：按照每个物
品给出的顺序，把它装入第一个能够容纳它的箱子；如果这样的箱子不存在，就把该物
品放在一个新箱子里，并将该箱子房子箱子列表的尾部。
1）证明FF算法是一个2近似的算法
装箱问题还有一个降序优先容纳算法（first-fit decreasing,FFD）：它在开始的时候
，对物品按照体积的降序进行排序，然后再执行有限容纳算法。
2）这是个几近似算法？证明之。
题目来源：
（美）Anany Levitin
Introdution to The Design and Analysis of Algorithms
approximation algorithm
This 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.
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.
Huasing Association 1999 - 2013