近似装箱问题（三种联机算法实现） 源代码, 箱子

yuyang911220

【0】README0.1） 本文总结于 数据结构与算法分析， 源代码均为原创， 旨在 理解 “近似装箱问题（三种联机算法实现）” 的idea 并用源代码加以实现；
0.2） 近似装箱问题的三种联机算法 分别是： 下项适合算法 + 首次适合算法 + 最佳适合算法 ， 我们将依次给出源代码实现+算法描述；
0.2）联机问题+脱机问题

• version1）联机装箱问题： 在这种问题中， 必须将每一件物品放入一个箱子后才处理下一件物品；（英语口语考试， 做完上一题，才能进入下一题作答）
• version2）脱机装箱问题：在一个脱机装箱算法中， 我们做任何事情 都需要等到所有的输入数据全被读入后才进行；（一般的考试，你只需要在规定的时间做完题目即可，做题顺序不是我们所关心的）

【1】近似装箱问题1.1）问题描述： 给定N 项物品， 大小为 s1, s2, ..., sN， 所有的大小都满足 0 < si < = 1 ；问题是要把这些物品装到最小数目的箱子中去， 已知每个箱子的容量是1个单位；下图显示的是 对N项物品的最优装箱方法；

1.2）有两种版本的装箱问题：

• version1）联机装箱问题： 在这种问题中， 必须将每一件物品放入一个箱子后才处理下一件物品；（英语口语考试， 做完上一题，才能进入下一题作答）
• version2）脱机装箱问题：在一个脱机装箱算法中， 我们做任何事情 都需要等到所有的输入数据全被读入后才进行；（一般的考试，你只需要在规定的时间做完题目即可，做题顺序不是我们所关心的）

1.3）联机算法

• 1.3.1）要考虑的第一个问题是： 一个联机算法即使在允许无限计算的情况下是否实际上总能给出最优的解答；我们知道， 即使允许无限计算， 联机算法也必须先放入一项物品然后才能处理下一件物品并且不能改变决定
• 1.3.2）我们可以证明：联机算法不总能够给出最优解；

【2】下项适合算法2.1）算法描述： 当处理任一物品时， 我们检查看他是否还能装进刚刚装进物品的同一个箱子中去。 如果能够装进去， 那么就把它装入该箱子中， 否则，就开辟一个新箱子；
2.2）看个荔枝：


2.3）source code + printing results

• 2.3.1）download source code： https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter10/p271_nextFit
• 2.3.2）source code at a glance：（for complete code , please click the given link above）

void nextfix(double key, int* index){    int i;    ElementTypePtr box;    ElementTypePtr temp;    box = buildSingleElement();    box->key = key; // build single box with key over        i = *index;    for(; i<size; i++)    {        if(surplus < key)            continue;        temp = boxes ;        while(temp->next)                               temp = temp->next;        temp->next = box;        surplus -= key;        break;    }    *index = i;}

• 2.3.3）printing results：