c_cppÑ个作业1,2，...，n要在由2台机器m1和m2组成的流水线上完成加工。每个作业加工的顺序都是先在m1上加工，然后在m2上加工.m1和m2加工作业我所需的时间分别为ai和璧(代码

关键词：

//3d9 动态规划 流水作业调度问题
#include "stdafx.h"
#include <iostream> 
using namespace std; 
 
const int N = 5;
 
class Jobtype

	public:
		int operator <=(Jobtype a) const
		
			return(key<=a.key);
		
		int key,index;
		bool job;
;
 
int FlowShop(int n,int a[],int b[],int c[]);
void BubbleSort(Jobtype *d,int n);//本例采用冒泡排序
 
int main()

	int a[] = 2,4,3,6,1;
	int b[] = 5,2,3,1,7;
	int c[N];
 
	int minTime =  FlowShop(N,a,b,c);
 
	cout<<"作业在机器1上的运行时间为："<<endl;
	for(int i=0; i<N; i++)
	
		cout<<a[i]<<" ";
	
	cout<<endl;
	cout<<"作业在机器2上的运行时间为："<<endl;
	for(int i=0; i<N; i++)
	
		cout<<b[i]<<" ";
	
	cout<<endl;
 
	cout<<"完成作业的最短时间为："<<minTime<<endl;
	cout<<"编号从0开始，作业调度的顺序为："<<endl;
	for(int i=0; i<N; i++)
	
		cout<<c[i]<<" ";
	
	cout<<endl;
	return 0;

 
int FlowShop(int n,int a[],int b[],int c[])

	Jobtype *d = new Jobtype[n];
	for(int i=0; i<n; i++)
	
		d[i].key = a[i]>b[i]?b[i]:a[i];//按Johnson法则分别取对应的b[i]或a[i]值作为关键字
		d[i].job = a[i]<=b[i];//给符合条件a[i]<b[i]的放入到N1子集标记为true
		d[i].index = i;
	
 
	BubbleSort(d,n);//对数组d按关键字升序进行排序
 
	int j = 0,k = n-1;
 
	for(int i=0; i<n; i++)
	
		if(d[i].job)
		
			c[j++] = d[i].index;//将排过序的数组d，取其中作业序号属于N1的从前面进入
		
		else
		
			c[k--] = d[i].index;//属于N2的从后面进入，从而实现N1的非减序排序，N2的非增序排序
		
	
 
	j = a[c[0]];
	k = j+b[c[0]];
	for(int i=1; i<n; i++)
	
		j += a[c[i]];//M1在执行c[i]作业的同时，M2在执行c[i-1]号作业，最短执行时间取决于M1与M2谁后执行完
		k = j<k?k+b[c[i]]:j+b[c[i]];//计算最优加工时间
	
 
	delete d;
	return k;

 
//冒泡排序
void BubbleSort(Jobtype *d,int n)

	int i,j,flag; 
	Jobtype temp;
 
	for(i=0;i<n;i++)  
		flag = 0;  
		for(j=n-1;j>i;j--)  
			//如果前一个数大于后一个数，则交换  
			if(d[j]<=d[j-1])  
				temp = d[j];  
				d[j] = d[j-1];  
				d[j-1] = temp;  
				flag = 1;  
			  
		  
		//如果本次排序没有进行一次交换，则break，减少了执行之间。  
		if(flag == 0)  
			break;  
		  
	

c_cpp给定Ñ个作业的集合j1，j2，......，jn。每个作业必须先由机器1处理，然后由机器2处理。作业籍需要机器ĵ的处理时间为tji。对于一个确定的作业调度，设fji是作业我在(代码

查看详情

c_cpp给定Ñ个顶点的多边形，每个顶点标有一个整数，每条边上标有+（加）或是×（乘）号，并且Ñ条边按照顺时针依次编号为1〜n的给出。了一个n=4个顶点的多边形。游(代码

查看详情

c_cpp给定Ñ个矩阵：a1，a2，...，an，其中艾与艾+1是可乘的，i=1,2，...，n-1确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数(代码片

查看详情

c_cpp设有Ñ个活动的集合e=1,2，...，n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源每个。活动i都有一个要求使用该资源的起始时(代码片段

查看详情

c_cpp求数字Ñ中1的个数(代码片段)

查看详情

c_cpp一队士兵在操场上排成一列，士兵总数为n，士兵按照队伍从前往后的顺序从1到Ñ依次编号。每个士兵有各自的身高，第i个士兵的身高为ai。士兵列队完毕后，将军走到队列的最前面。因为身高不(

查看详情

c_cpp面试题17：打印从1到最大的Ñ位数(代码片段)

查看详情

c_cpp用两个数组来表示所给的含有Ñ个元素的有序集s.用值[0：n]存储有序集中的元素，链接[0：n]存储有序集中元素在数组值中位置的指针（实际上使用数组模拟链表）。链路[0]指向有序集(

查看详情

c_cpp在n×n的格的棋盘上放置彼此不受攻击的Ñ个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子.n后问题等价于在n×n的格的棋盘上放(

查看详情

c_cpp209.cpp(代码片段)

查看详情

c_cpp如果用有序链表来表示一个含有Ñ个元素的有序集s，则在最坏情况下，搜索小号中一个元素需要o（n）的计算时间。提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜(

查看详情

回溯法批处理作业调度问题

问题：给定n个作业的集合J1,J2,…,Jn。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需(1≤i≤n)要机器j(1≤j≤2)的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在... 查看详情

5作业

  3.奇偶归一猜想——对于每一个正整数，如果它是奇数，则对它乘3再加1，如果它是偶数，则对它除以2，如此循环，最终都能够得到1。   如n=11，得序列：11,34,17,52,26,13,40,20,10,5,16,8,4,2,1。(共有14个步骤) &nbs... 查看详情

codeforces209ctrailsandglades[构造](代码片段)

欧拉回路是经过所有边仅一次无向图有欧拉回路的条件是:每个点的度数都是偶数并且图连通（可以有孤立点）#include<cstdio>#defineN1000007intf[N],I[N],d[N],n,m,u,v,A;intF(intx)returnx==f[x]?x:f[x]=F(f[x]);intmain()d[1]=2;//孤立点不需要连边但一定... 查看详情

c_cpp有一批共Ñ个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱我的重量为wi，装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。如果有，找出一种装载方案(

查看详情

c_cpp“linux的环境高级编程”作业2(代码片段)

查看详情

实验4贪心法（作业调度问题）(代码片段)

1.问题的已知设有n个独立的作业1,2,…,n，由m台相同的机器M1,M2,…,Mm进行加工处理，作业i所需的处理时间为ti（1≤i≤n），每个作业均可在任何一台机器上加工处理，但不可间断、拆分。2.所求的目标要求给... 查看详情

209.minimumsizesubarraysum

Givenanarrayof n positiveintegersandapositiveinteger s,findtheminimallengthofasubarrayofwhichthesum≥ s.Ifthereisn‘tone,return0instead.Forexample,giventhearray [2,3,1,2,4,3] 查看详情