动态规划算法——双机调度问题

问题

问题描述:

用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理,则需要时间bi。

由于各作业的特点和机器的性能关系，很可能对于某些i，有ai ≥ bi，而对于某些j ≠ i，有aj < bj。既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。

研究一个实例:

(a1, a2, a3, a4, a5, a6) = (2, 5, 7, 10, 5, 2)

(b1, b2, b3, b4, b5, b6) = (3, 8, 4, 11, 3, 4)

算法设计:

对于给定的n个作业，找出一个最优调度方案，使A、B两台机器处理完这n个作业的时间最短。

数据输入:

由文件input. txt提供输入数据。

文件的第1行是1个正整数n,表示要处理n个作业

在接下来的2行中,每行有n个正整数，分别表示处理机A和B处理第i个作业需要的处理时间。

结果输出:

将计算出的最短处理时间输出到文件output txt。

• 输入文件示例

  input.txt
  
  6
  2 5 7 10 5 2
  3 8 4 11 3 4

• 输出文件示例

  output.txt
  
  15

算法思路

• 找出n个任务所有耗时中最大的数m，也就是A和B数组的最大值。
• 设置三维布尔量数组p[mn][mn][n]，布尔量p[i][j][k]表示前k个作业可以在处理机A用时不超过i，处理机B不超过j的时间内完成。动态规划算法：p[i][j][k] = p[i-ak][j][k-1] | p[i][j-bk][k-1]（|为按位与运算符）
• 由上一步所得的结果我们可以找到时间最短的答案，具体是遍历布尔量为1的k = n的数组，取min(i, j)，如果比前一个小则取这个
• 具体算法如下

代码

#include<bits/stdc++.h>
using namespace std;

void read( )
{
	ifstream infile ;
	infile.open( "input.txt" ) ;
	infile >> n ;
	
	a = new int[n] ;
	b = new int[n] ;
	
	for( int i = 0 ; i < n ; i ++ )
	{
		infile >> a[i] ;
		m = max( a[i] , m ) ;
	}
	for( int i = 0 ; i < n ; i ++ )
	{
		infile >> b[i] ;
		m = max( b[i] , m ) ;
	}
	mn = m * n ;
	
	infile.close();
}
void dyna()
{
	bool*** p = new bool** [mn+1] ;
	for( int i = 0 ; i <= mn ; i ++ )
	{
		p[i] = new bool* [mn+1] ;
		for( int j = 0 ; j <= mn ; j++ )
		{
			p[i][j] = new bool [n+1] ;
			p[i][j][0] = true ;
			for( int k = 1 ; k <= n ; k ++ )
			{
				p[i][j][k] = false ;
			}
		}
	}
	for( int k = 1 ; k <= n ; k ++ )
	{
		for( int i = 0 ; i <= mn ; i++ )
		{
			for( int j = 0 ; j <= mn ; j++)
			{
				if( i - a[k-1] >= 0 ) p[i][j][k] = p[i-a[k-1]][j][k-1] ;
				if( j - b[k-1] >= 0 ) p[i][j][k] = p[i][j][k] || p[i][j-b[k-1]][k-1] ;
			}
		}
	}
	int opt = mn ;
	for( int i = 0 ; i <= mn ; i ++ )
	{
		for( int j= 0 ; j <= mn ; j++ )
		{
			if( p[i][j][n] )
			{
				int tmp = max( i , j ) ;
				if( tmp < opt ) opt = tmp ;
			}
		}
	}
	ofstream outfile ;
	outfile.open( "output.txt" ) ;
	outfile << opt << endl ;
 	outfile.close();
}
int main()
{
	read() ;
	dyna() ;
    return 0 ;
}

总结

上述算法的时间复杂度为O(m2n3)