做饰品网站,就业前景好的专业排名,seo刷排名软件,北京设计网站试题四#xff08;共15分#xff09;
阅读下列说明和C代码#xff0c;回答问题1至问题3#xff0c;将解答写在答题纸的对应栏内。
【说明】
设有n个货物要装入若干个容量为C的集装箱以便运输#xff0c;这n个货物的体积分别为{S1,S2,#xff0e;#xff0e;#xff…试题四共15分
阅读下列说明和C代码回答问题1至问题3将解答写在答题纸的对应栏内。
【说明】
设有n个货物要装入若干个容量为C的集装箱以便运输这n个货物的体积分别为{S1,S2,Sn}且有si≤C(1≤i≤ n)。为节省运输成本用尽可能少的集装箱来装运这n个货物。
下面分别采用最先适宜策略和最优适宜策略来求解该问题。
最先适宜策略( firstfit)首先将所有的集装箱初始化为空对于所有货物按照所给的次序每次将一个货物装入第一个能容纳它的集装箱中。
最优适宜策略( bestfit)与最先适宜策略类似不同的是总是把货物装到能容纳它且目前剩余容量最小的集装箱使得该箱子装入货物后闲置空间最小。
【C代码】
下面是这两个算法的C语言核心代码。
(1)变量说明 n货物数 C集装箱容量 s数组长度为n其中每个元素表示货物的体积下标从0开始 b数组长度为nb[i]表示第i1个集装箱当前已经装入货物的体积下标从0开始 ij循环变量 k所需的集装箱数 min当前所用的各集装箱装入了第i个货物后的最小剩余容量 m当前所需要的集装箱数 temp临时变量
#include stdio.h
#include stdlib.h
#define n 10 //这个根据货物个数需要每次手动设置
#define C 10 //这个根据箱子的容量每次手动设置int firstfit (int t[]){int i,j;int k 0;int s[n], b[n];for(i 0; i n; i){b[i] 0; //0表示第i1个集装箱未装任何货物s[i] t[i];}for(i 0; i n; i) {j 0;while(C - b[j] s[i]){ //第i1个集装箱剩余容量与下一个货物体积进行比较j; //集装箱剩余空间小于下一个货物体积则选择下一个集装箱进行装载货物}b[j] b[j] s[i]; //集装箱当剩余前容量装入货物体积// printf(b[%d]%d\t, j, b[j]); //要看每个箱子怎么装的可以解开注释看下k k (j 1) ? k : (j 1);}return k;
}int bestfit(int t[]){int i, j, min, m, temp;int k 0;int b[n], s[n];for (i 0 ; i n; i) {b[i] 0;s[i] t[i];}for (i 0; i n; i) {min C;m k 1;for (j 0; j k 1; j) {temp C - b[j] - s[i];if (temp 0 temp min) {min temp;m j;}}b[m] b[m] s[i];// printf(b[%d]%d\t, m, b[m]); //要看每个箱子怎么装的可以解开注释看下k k (m 1) ? k : (m 1);}return k;
}int main() {int t[] {4, 2, 7, 3, 5, 4, 2, 3, 6, 2};int firstfit();int bestfit();int result1, result2;result1 firstfit(t);printf(firstfit需要%d个集装箱\n, result1);result2 bestfit(t);printf(bestfit需要%d个集装箱\n, result2); return 1;
}【问题1】8分
根据【说明】和【C代码】填充C代码中的空(1)(4)。
【问题2】4分
根据【说明】和【C代码】该问题在最先适宜和最优适宜策略下分别采用了(5) 和(6)算法设计策略时间复杂度分别为 (7) 和 (8)用O符号表示。
【问题3】3分
考虑实例n 10C 10各个货物的体积为{4273542362}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为(9)和(10)。考虑一般的情况这两种求解策略能否确保得到最优解(11) 能或否
