静态网站公用头部 调用标题,微信分销网站建设,宿迁房产网安居客,建站公司佛山目录
一、活动安排问题
二、最优装载问题
三、分数背包问题
四、多机调度问题 一、活动安排问题
1、策略 活动安排问题#xff1a;设有n个活动的集合E{1,2,...,n}#xff0c;每个活动i都有一个使用该资源的起始时间和一个结束时间#xff0c;且。如果选择了活动i则它在…目录
一、活动安排问题
二、最优装载问题
三、分数背包问题
四、多机调度问题 一、活动安排问题
1、策略 活动安排问题设有n个活动的集合E{1,2,...,n}每个活动i都有一个使用该资源的起始时间和一个结束时间且。如果选择了活动i则它在时间区间内占用资源如何在有限的时间内选择最多的活动方案安排。 解法按结束时间优先的贪心算法。
1 如果活动i和活动j能够相容假设活动i在活动j之前那么一定有。
2按照序列对和同时进行排序保证两者对应。排序可以使用快速排序、归并排序和堆排复杂度为Onlogn。
3第1个活动最小所以进入活动安排其他如果存在则ij移动活动安排。 给定一个活动序列 的关系 2、代码
//活动安排
import java.util.Scanner;
public class activityarrangement {public static void main(String[] args){int nnew Scanner(System.in).nextInt();int s[]new int[n];int f[]new int[n];for(int i0;in;i)s[i]new Scanner(System.in).nextInt();for(int i0;in;i)f[i]new Scanner(System.in).nextInt();quickSort(f,s, 0, n-1);GreedySelector(s,f);}public static void GreedySelector(int s[],int f[]) {System.out.println(s[0] f[0]);int j0;for(int i1;is.length;i){if(s[i]f[j]){System.out.println(s[i] f[i]);ji;}}}
二、最优装载问题
1、策略 有一批集装箱要装上一艘载重为c的轮船集装箱i的重量为要求装载体积不受限制情况下将尽可能多的集装箱装上轮船。 利用贪心算法重量最轻的集装箱优先装载直到轮船载重无法继续装入集装箱。 排序方法可以使用快排、归排和堆排来降低时间复杂度。 约束条件和目标函数如下 例题如下 2、代码
//最优装载问题
public static void main(String []args) {int c400;int weights[]{100,200,50,90,150,50,20,80};quickSort(weights,0,weights.length-1);System.out.println(load(weights,c));}
public static int load(int weights[],int c){int tmpc;for(int i0;iweights.length;i){if(cweights[i]){c-weights[i];}}return tmp-c;}
三、分数背包问题
1、策略 分数背包问题在0-1背包的问题基础上可以每个物品装一部分即0~1背包问题要求在有限的容量基础上求解装有物品的最高总价值。 策略以单位重量价值最高的优先的贪心算法。 建立a数组单位重量下价值以a数组为排序依据同时排序awv数组计算a数组较大值优先的情况下能产生的最大总价值。 例题如下 2、代码
省略排序过程
//分数背包问题
public class dividebackage {
public static void main(String[] args){int n3;int c20;double w[]{18,15,10};double v[]{25,24,15};double a[]new double[n];for(int i0;in;i)a[i]v[i]/w[i];quickSort(a,w,v,0,w.length-1);System.out.println(maximum(a,w,v,c));}
public static double maximum(double a[],double w[],double v[],int c){double value0;int weight0;for(int ia.length-1;i0;i--){if((c-weight)w[i]){valuev[i];weightw[i];}else{valuev[i]*(c-weight)/w[i];break;}}return value;}
}
四、多机调度问题
1、概述 多机调度问题设有n个独立作业由m台相同机器进行加工处理作业i所需的处理时间为,每个作业均可以在任何一台机器上加工处理但不可间断、拆分。设计一种算法使得n个作业在尽可能短的时间内由m台机器加工处理完成。 策略按任务时间较长的进行贪心算法设定timepdms五个数组定义看下面代码注释首先对time数组和p数组按任务时间降序排序快排调度问题为添加任务和时间推移两个阶段循环进行直到任务不再添加所有机器还需占用时间数为0则退出调度问题。 添加任务遍历每一个机器若当前机器m还需占用时间为0且仍有任务i需要添加则将任务i添加到机器m机器m的所做任务数加一机器m执行任务添加任务i编号。 时间推移时间后移一每个任务的还需所占用时间减一若每个机器的所占用时间都为0且没有新任务添加则退出调度问题返回当前时间。若存在机器i所占用时间为0但仍有其他机器任务未结束则机器i占用时间不再减少避免出现负数。 下面例题解决效果 2、代码
//多机调度问题
public class multimachine {public static void main(String[] args){int time[]{2,14,4,16,6,5,3}; //每个任务所占时间int p[]{1,2,3,4,5,6,7}; //任务编号int d[]{0,0,0}; //当前机器还需占用时间数int m[]{0,0,0}; //每个机器执行了几个任务int s[][]new int[d.length][time.length]; //每个机器执行了哪些任务//对时间列和任务编号进行重新排序quickSort(time,p,0,time.length-1);//输出多机调度总时间deploy(time,p,d,s,m);//输出每个机器执行了哪些任务for(int i0;id.length;i){for(int j0;jtime.length;j){if(s[i][j]0)break;System.out.print(s[i][j] );}System.out.println();}} public static void deploy(int time[],int p[],int d[],int s[][],int m[]){int tot0;int c0; //总作业序列顺序执行到几个while(true){//进入任务增加每个机器的所占用时间for(int i0;id.length;i){if(d[i]0ctime.length){d[i]time[c];s[i][m[i]]p[c];}}tot1;int zero0;//时间推移加一减少每个机器的所占用时间for(int i0;id.length;i){if(d[i]0)break;d[i]--;zerod[i];}//若每个机器都为0且没有任务继续添加则终止调度if(zero0)break;}System.out.println(tot);}
