| 箱子装载问题的算法研究 |
| |
| 引用本文： | 杜立智.箱子装载问题的算法研究[J].四川大学学报(自然科学版),2003,40(2):392-394. |
| |
| 作者姓名： | 杜立智 |
| |
| 作者单位： | 武汉科技大学计算机科学与技术学院,武汉,430081 |
| |
| 摘 要： | 1 引言 设有ｎ件物品 ,每件物品的体积分别为ｓ1,ｓ2 ,… ,ｓｎ,且 0 <ｓｉ≤ 1(ｉ =1,2 ,… ,ｎ) .现有一批箱子 ,每只箱子的容量为一个单位 ,现在的问题是能够容纳这ｎ件物品的箱子至少需多少只 ?此问题为著名的ＮＰ复杂问题 ,迄今在多项式时间内尚无求解的办法 .但可用近似算法求解 ,使结果接近最优解 .对于此问题 ,有 4种流行的求解算法 :( 1)最先匹配法 (ＦｉｒｓｔＦｉｔ ,ＦＦ) ;( 2 )最优匹配法 (ＢｅｓｔＦｉｔ ,ＢＦ) ;( 3)最先匹配递减法 (ＦＦＤ) ;( 4 )最优匹配递减法 (ＢＦＤ) .这 4种算法的时间复杂度均为Ｏ(ｎ×ｌｏｇ(…
|
| 关 键 词： | 箱子装载问题 NP复杂问题 近似算法 最优解 类贪婪算法 时间复杂度 |
| 文章编号： | 0490-6756(2003)02-0293-03 |
The Algorithm Research for Optimal Packing |
| |
| DU Li,zhi.The Algorithm Research for Optimal Packing[J].Journal of Sichuan University (Natural Science Edition),2003,40(2):392-394. |
| |
| Authors: | DU Li zhi |
| |
| Abstract: | Case Packing is a famous NP problem. Author designed a approximate algorithm to solve this problem. This algorithm can analyze the performance bounds more deeply than traditional algorithms. Also, it has a good worst case performance bounds. |
| |
| Keywords: | NP problem optimal packing performance bounds |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
