|
|
|
|
|
|
|
复制本帖HTML代码
|
|
高亮:
今天贴
X 昨天贴
X 前天贴
X |
一个junior问我一个算法的问题，可是我的算法是用英文学的，看不懂他的题干。哪位曾经用中文学过算法的朋友帮个忙吧。谢谢~~
请考虑装箱问题的贪婪算法，他也被称为优先容纳算法（first-fit,FF）：按照每个物
品给出的顺序，把它装入第一个能够容纳它的箱子；如果这样的箱子不存在，就把该物
品放在一个新箱子里，并将该箱子房子箱子列表的尾部。
1）证明FF算法是一个2近似的算法
装箱问题还有一个降序优先容纳算法（first-fit decreasing,FFD）：它在开始的时候
，对物品按照体积的降序进行排序，然后再执行有限容纳算法。
2）这是个几近似算法？证明之。
题目来源：
（美）Anany Levitin
Introdution to The Design and Analysis of Algorithms .
|
| 欢迎来到华新中文网，踊跃发帖是支持我们的最好方法! |
|
|
－