郑州正规的网站制作价钱,工信部网站备案查询,细分网站,企业形象设计包括什么【0】README
0.1#xff09; 本文总结于 数据结构与算法分析#xff0c; 源代码均为原创#xff0c; 旨在 理解 “近似装箱问题#xff08;三种联机算法实现#xff09;” 的idea 并用源代码加以实现#xff1b; 0.2#xff09; 近似装箱问题的三种联机算法 分别是 本文总结于 数据结构与算法分析 源代码均为原创 旨在 理解 “近似装箱问题三种联机算法实现” 的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.3source code printing results
2.3.1download source code https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter10/p271_nextFit2.3.2source code at a glancefor 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 overi *index;for(; isize; i){if(surplus[i] key)continue;temp boxes[i] ;while(temp-next) temp temp-next;temp-next box;surplus[i] - key;break;}*index i;
}
2.3.3printing results 【3】首次适合算法
3.0出现的问题虽然下项算法有一个合理的性能保证但是它的效果在实践中是很差的因为在不需要开辟新箱子的时候它却开辟了新箱子 3.1算法描述首次适合算法的策略是 依序扫描这些箱子但吧新的一项物品放入足够盛下它的第一个箱子中。因此只有当先前放置物品的结果已经没有再容得下当前物品余地的时候 我们才开辟一个新箱子一句话 这里是从头到尾扫描箱子 3.2看个荔枝 3.3可以断言首次适合算法保证其解最多包含最优装箱数的二倍因为在任一时刻最多有一个箱子其空出的部分大于箱子的一半因为若有第二个这样的箱子 则它装的物品就会装到第一个这样的箱子中了 3.4source code printing results
3.4.1download source code https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter10/p272_firstFit3.4.2source code at a glancefor complete code , please click the given link above
void firstFix(double key)
{int i;ElementTypePtr box;ElementTypePtr temp;box buildSingleElement();box-key key; // build single box with key overfor(i0; isize; i){if(surplus[i] key)continue;temp boxes[i] ;while(temp-next) temp temp-next;temp-next box;surplus[i] - key;break;}
}
3.4.3printing results 【4】最佳适合算法
4.1算法描述该方法不是吧一项新物品放入所发现的第一个能够容纳它的箱子 而是放到所有箱子中能够容纳它的最满的箱子中 4.2看个荔枝 Attention
A1大小为0.3 的项不是放在B2 而是放在了B3 此时它正好把B3填满A2当需要O(NlogN)的时候 该算法对随机的输入表现得很好
4.3source code printing results
2.1download source code https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter10/p273_bestFit2.2source code at a glancefor complete code , please click the given link above
void bestFix(double key)
{int i;ElementTypePtr box;ElementTypePtr temp;double minimum;int miniIndex;box buildSingleElement();box-key key; // build single box with key overminiIndex 0;minimum 1.0;for(i0; isize; i){if(surplus[i] key)continue;if(surplus[i] - key minimum){minimum surplus[i] - key;miniIndex i;}}temp boxes[miniIndex] ;while(temp-next) temp temp-next;temp-next box;surplus[miniIndex] - key;
}
2.3printing results
