正文 

当前位置： 首页 > 开发 > java教程

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

author author     2023-01-09     721

关键词： 

#include <iostream>
 
template<class Type>
class Graph;
 
template<class T> 
class MinHeap 
 
	template<class Type>
	friend class Graph;
	public: 
		MinHeap(int maxheapsize = 10); 
		~MinHeap()delete []heap; 
 
		int Size() constreturn currentsize; 
		T Max()if(currentsize) return heap[1]; 
 
		MinHeap<T>& Insert(const T& x); 
		MinHeap<T>& DeleteMin(T &x); 
 
		void Initialize(T x[], int size, int ArraySize); 
		void Deactivate(); 
		void output(T a[],int n);
	private: 
		int currentsize, maxsize; 
		T *heap; 
; 
 
template <class T> 
void MinHeap<T>::output(T a[],int n) 
 
	for(int i = 1; i <= n; i++) 
	cout << a[i] << " "; 
	cout << endl; 
 
 
template <class T> 
MinHeap<T>::MinHeap(int maxheapsize) 
 
	maxsize = maxheapsize; 
	heap = new T[maxsize + 1]; 
	currentsize = 0; 
 
 
template<class T> 
MinHeap<T>& MinHeap<T>::Insert(const T& x) 
 
	if(currentsize == maxsize) 
	 
		return *this; 
	 
	int i = ++currentsize; 
	while(i != 1 && x < heap[i/2]) 
	 
		heap[i] = heap[i/2]; 
		i /= 2; 
	 
 
	heap[i] = x; 
	return *this; 
 
 
template<class T> 
MinHeap<T>& MinHeap<T>::DeleteMin(T& x) 
 
	if(currentsize == 0) 
	 
		cout<<"Empty heap!"<<endl; 
		return *this; 
	 
 
	x = heap[1]; 
 
	T y = heap[currentsize--]; 
	int i = 1, ci = 2; 
	while(ci <= currentsize) 
	 
		if(ci < currentsize && heap[ci] > heap[ci + 1]) 
		 
			ci++; 
		 
 
		if(y <= heap[ci]) 
		 
			break; 
		 
		heap[i] = heap[ci]; 
		i = ci; 
		ci *= 2; 
	 
 
	heap[i] = y; 
	return *this; 
 
 
template<class T> 
void MinHeap<T>::Initialize(T x[], int size, int ArraySize) 
 
	delete []heap; 
	heap = x; 
	currentsize = size; 
	maxsize = ArraySize; 
 
	for(int i = currentsize / 2; i >= 1; i--) 
	 
		T y = heap[i]; 
		int c = 2 * i; 
		while(c <= currentsize) 
		 
			if(c < currentsize && heap[c] > heap[c + 1]) 
				c++; 
			if(y <= heap[c]) 
				break; 
			heap[c / 2] = heap[c]; 
			c *= 2; 
		 
		heap[c / 2] = y; 
	 
 
 
template<class T> 
void MinHeap<T>::Deactivate() 
 
	heap = 0; 
 

//批作业调度问题 优先队列分支限界法求解 
#include "stdafx.h"
#include "MinHeap2.h"
#include <iostream>
using namespace std;
 
class Flowshop;
class MinHeapNode

	friend Flowshop;
	public:
		operator int() const
		
			return bb;
		
	private:	
		void Init(int);
		void NewNode(MinHeapNode,int,int,int,int);
		int s,			//已安排作业数
			f1,			//机器1上最后完成时间
			f2,			//机器2上最后完成时间
			sf2,		//当前机器2上完成时间和
			bb,			//当前完成时间和下界
			*x;			//当前作业调度
;
 
class Flowshop

	friend int main(void);
	public:
		int BBFlow(void);
	private:
		int Bound(MinHeapNode E,int &f1,int &f2,bool **y);
		void Sort(void);
		int n,			//作业数
			** M,		//各作业所需的处理时间数组
			**b,		//各作业所需的处理时间排序数组
			**a,		//数组M和b的对应关系数组
			*bestx,		//最优解
			bestc;		//最小完成时间和
		bool **y;		//工作数组
;
 
template <class Type>
inline void Swap(Type &a, Type &b);
 
int main()

	int n=3,bf;
	int M1[3][2]=2,1,3,1,2,3;
 
	int **M = new int*[n];
	int **b = new int*[n];
	int **a = new int*[n];
	bool **y = new bool*[n];
	int *bestx = new int[n];  
 
    for(int i=0;i<=n;i++)
	
        M[i] = new int[2];
		b[i] = new int[2];
		a[i] = new int[2];
		y[i] = new bool[2];
	
	cout<<"各作业所需要的时间处理数组M(i,j)值如下："<<endl;
 
	for(int i=0;i<n;i++)
	
		for(int j=0;j<2;j++)
		
			M[i][j]=M1[i][j];
		
	
 
    for(int i=0;i<n;i++)
	
		cout<<"(";
		for(int j=0;j<2;j++)
		cout<<M[i][j]<<" ";
		cout<<")";
	
	cout<<endl;
 
	Flowshop flow;
	flow.n = n;
	flow.M = M;
	flow.b = b;
	flow.a = a;
	flow.y = y;
	flow.bestx = bestx;
	flow.bestc = 1000;//给初值
 
	flow.BBFlow();
 
	cout<<"最优值是："<<flow.bestc<<endl;
	cout<<"最优调度是：";
 
	for(int i=0;i<n;i++)
	
		cout<<(flow.bestx[i]+1)<<" ";
	
	cout<<endl;
 
	for(int i=0;i<n;i++)
	
		delete[] M[i];
		delete[] b[i];
		delete[] a[i];
		delete[] y[i];		
	
	return 0;

 
//最小堆节点初始化
void MinHeapNode::Init(int n)

	x = new int[n];
	for(int i=0; i<n; i++)
	
		x[i] = i;
	
	s = 0;
	f1 = 0;
	f2 = 0;
	sf2 = 0;
	bb = 0;

 
//最小堆新节点
void MinHeapNode::NewNode(MinHeapNode E,int Ef1,int Ef2,int Ebb,int n)

	x = new int[n];
	for(int i=0; i<n; i++)
	
		x[i] = E.x[i];
	
	f1 = Ef1;
	f2 = Ef2;
	sf2 = E.sf2 + f2;
	bb = Ebb;
	s =  E.s + 1;

 
//对各作业在机器1和2上所需时间排序
void Flowshop::Sort(void)

	int *c = new int[n];
	for(int j=0; j<2; j++)
	
		for(int i=0; i<n; i++)
		
			b[i][j] = M[i][j];
			c[i] = i;
		
 
		for(int i=0; i<n-1; i++)
		
			for(int k=n-1; k>i; k--)
			
				if(b[k][j]<b[k-1][j])
				
					Swap(b[k][j],b[k-1][j]);
					Swap(c[k],c[k-1]);
				
			
			
 
		for(int i=0; i<n; i++)
		
			a[c[i]][j] = i;
		
	
 
	delete []c;

 
//计算完成时间和下界
int Flowshop::Bound(MinHeapNode E,int &f1,int &f2,bool **y)

	for(int k=0; k<n; k++)
	
		for(int j=0; j<2; j++)
			
			y[k][j] = false;
		
	
 
	for(int k=0; k<=E.s; k++)
	
		for(int j=0; j<2; j++)
		
			y[a[E.x[k]][j]][j] = true;
		
	
 
	f1 = E.f1 + M[E.x[E.s]][0];
	f2 = ((f1>E.f2)?f1:E.f2)+M[E.x[E.s]][1];
	int sf2 = E.sf2 + f2;
	int s1 = 0,s2 = 0,k1 = n-E.s,k2 = n-E.s,f3 = f2;
 
	//计算s1的值
	for(int j=0; j<n; j++)
	
		if(!y[j][0])
		
			k1--;
			if(k1 == n-E.s-1)
			
				f3 = (f2>f1+b[j][0])?f2:f1+b[j][0];
			
			s1 += f1+k1*b[j][0];
		
	
 
	//计算s2的值
	for(int j=0; j<n; j++)
		
		if(!y[j][1])
		
			k2--;
			s1 += b[j][1];
			s2 += f3 + k2*b[j][1];
		
	
 
	//返回完成时间和下界
	return sf2 +((s1>s2)?s1:s2);

 
//解批处理作业调度问题的优先队列式分支限界法
int Flowshop::BBFlow(void)

	Sort();//对各作业在机器1和2上所需时间排序
	MinHeap<MinHeapNode> H(1000);
 
	MinHeapNode E;
	//初始化
	E.Init(n);
	//搜索排列空间树
	while(E.s<=n)
	
		//叶节点
		if(E.s == n)
		
			if(E.sf2<bestc)
			
				bestc = E.sf2;
				for(int i=0; i<n; i++)
				
					bestx[i] = E.x[i];
				
			
			delete []E.x;
		
		else//产生当前扩展节点的儿子节点
		
			for(int i=E.s; i<n; i++)
			
				Swap(E.x[E.s],E.x[i]);
				int f1,f2;
				int bb = Bound(E,f1,f2,y);
				if(bb<bestc)
				
					//子树可能含有最优解
					//节点插入最小堆
					MinHeapNode N;
					N.NewNode(E,f1,f2,bb,n);
					H.Insert(N);
				
				Swap(E.x[E.s],E.x[i]);
			
			delete []E.x;//完成节点扩展
		
		if(H.Size() == 0)
		
			break;
		
		H.DeleteMin(E);//取下一扩展节点
	
	return bestc;

 
template <class Type>
inline void Swap(Type &a, Type &b)
 
	Type temp=a; 
	a=b; 
	b=temp;

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

查看详情

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

查看详情

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

查看详情

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

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

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

查看详情

计算机操作系统实验指导(第3版)第四篇操作系统学习指导和习题解析第19章：调度与死锁习题和答案

...A.充分条件B.必要条件C.充分必要条件D.什么也不是设有4个作业同时到达,每个作业的执行时间是2min,它们在一台处理机上按单道方式运行,则平均周转时间为(B)。A.1minB.5minC.2.5minD.8min若系统中有8台绘图仪,有多个进程均需要使用两台,... 查看详情

c_cpp假设国家发行了Ñ种不同面值的邮票，并且规定每张信封上最多只允许贴米张邮票。连续邮资问题要求对于给定的Ñ和米的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，(

查看详情

c_cpp设r=r1，r2，...，rn是要进行排列的Ñ个元素，ri=r-ri。集合x中元素的全排列记为彼尔姆（x）。（ri）彼尔姆（x）表示在全排列perm（x）的每(代码片段)

查看详情

c_cpp给定一组单词，返回给定集合中的anagrams集合(代码片段)

查看详情

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

查看详情

c_cpp给定可能包含重复项的数字集合，返回所有可能的唯一排列。例如，[1,1,2]有以下内容(代码片段)

查看详情

c_cpp找到与给定值最近的k个元素(代码片段)

查看详情

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

查看详情

c_cpp209.cpp(代码片段)

查看详情

可抢占的优先级调度算法算例：cpu利用率

...处理器和两台外设IO1、IO2，现有3个优先级由高到低的作业J1、J2和J3都已装入了主存，它们使用资源的先后顺序和占用时间分别是：J1：IO2（30ms），CPU（10ms），IO1（30ms），CPU（... 查看详情

每组所需的最大行数

...oreachgroup【发布时间】：2021-11-0313:00:33【问题描述】：有1个表，其中所有这些记录都是为1名员工维护的。由于此表中还有一个列在此示例中未显示，因此该人对于甚至1个工作有多行，即工作J1有2行，工作J2有3行，工作J1也有2行... 查看详情

百度笔试复盘(代码片段)

按照短作业优先执行顺序，4个作业的执行顺序为J1、J4、J2、J3，执+行时间分别是3、（3+5）、（3+5+8）、（3+5+8+10），则平均周转时间为（3+（3+5&#x 查看详情

百度笔试复盘(代码片段)

按照短作业优先执行顺序，4个作业的执行顺序为J1、J4、J2、J3，执+行时间分别是3、（3+5）、（3+5+8）、（3+5+8+10），则平均周转时间为（3+（3+5&#x 查看详情