算法设计与分析——贪心算法——多机调度问题

系统管理员 2023-01-17 03:28 160阅读 0赞

该类问题可以使用贪心策略可以设计出较好的近似算法（并不是最优解）

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    typedef struct Node
    {
        
    	int hour;//记录该作业的所需要完成的时间
    	int number;//记录该作业在原来的序列的顺序
    }node;
    bool cmp(node x,node y)
    {
        
    	if(x.hour>y.hour)
    		return true;
    	else
    		return false;
    }
    void MultiMachine(Node node[], int machine_number, int *machine_operation, int *machine_time[],int job_number)
    	{
        
    	
    		int rear[job_number];
    	
    		//安排前机器数（机器的个数）个作业
    		for (int i = 0; i < machine_number;i++)
    		{
        
    			machine_time[i][0] = node[i].number;//将该作业放到二维数组中去
    			
    			rear[i] = 0;
    			
    			machine_operation[i] = node[i].hour;
    		}
    			cout<<"dsfdsjfklsdjflksdj";
    		//安排剩余的job_number-machine_number个作业
    		int i;
    		int j;
    		int k;
    		for( i= machine_number;i<job_number;i++)
    		{
        
    			for ( j = 0,k=1; k < machine_number;k++)//找到目前机器序列中使用时间最短的那台机器
    			{
        
    				if(machine_operation[j]>machine_operation[k])
    				{
        
    					j = k;
    				}
    			}
    			rear[j]++;
    			machine_time[j][rear[j]] = node[i].number;
    			machine_operation[j] += node[i].hour;
    
    		}
    	
    		for (int i = 0; i < machine_number;i++)
    		{
        
    			cout << "机器" << i + 1 << "处理：";
    			for (int j = 0; machine_time[i][j]>0;j++)
    			{
        
    				cout << "作业" << machine_time[i][j] << " ";
    
    			}
    			cout << "机器" << i << "的处理时间" << machine_operation[i] << endl;
    		}
    	}
    int main()
    {
        
    	cout << "输入待处理的作业个数：";
    	int job_number;
    	cin >> job_number;
    
    	Node node[job_number];
    	cout << "输入作业需要处理的时间：";
    	for (int i = 0; i < job_number;i++)
    	{
        
    		cin >> node[i].hour;
    		node[i].number = i + 1;
    	}
    
    	cout << "输入机器的个数：";
    	int machine_number;
    	cin >> machine_number;
    
    	sort(node, node + job_number, cmp);
    
    	int machine_time[machine_number][job_number];//记录每个机器上作业的序号 
    
    	int machine_operation[machine_number];//记录每个机器上已经的运行时间
    	for (int i = 0; i < machine_number;i++)
    	{
        
    		machine_operation[i] = 0;
    	}
    	MultiMachine(node, machine_number, machine_operation, (int**)machine_time, job_number);
    
    }