精华内容
下载资源
问答
  • 独立任务最优调度问题
    千次阅读
    2021-04-03 12:34:25

    动态规划 独立任务最优调度问题详解

    问题描述

    用2台处理机A和B处理n个作业。
    设第i个作业交给机器A处理时需要时间ai,若由机器B来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些i,有ai>=bi,而对于某些j,j≠i,有aj<bj。既不能将一个作业分开由2台机器处理,也没有一台机器能同时处理2个作业。
    设计一个动态规划算法,使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。
    研究一个实例: (a1,a2,a3,a4,a5,a6)=(2,5,7,10,5,2);(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)。 对于给定的2 台处理机A 和B处理n 个作业,找出一个最优调度方案,使2台机器处理完这n 个作业的时间最短。

    本文给出了三种解法,分别需要使用三维数组、二维数组、一维数组。代码在文章最后


    分析

    本问题乍一看似乎与动态规划没有什么关系。但是,我们可以注意到下面几点:

    1. 每个任务仅有两个选择:由A处理,或者由B处理。我们的目标是合理安排每个任务由哪个机器处理,从而找到最短的处理完所有任务的时间。
    2. 所有任务都是需要被处理的。这也就意味着,每个任务的处理顺序是无关紧要的。所以,为讨论的简单起见,我们可以从第一个任务开始,按顺序决定每个任务由哪个机器处理,直到处理完所有的任务。下文所有讨论都是按照顺序处理任务。

    由以上分析,我们至少可以想到一种解决问题的办法:穷举法。对于每个任务,都有两种选择,所以n个任务共2n种选择。我们可以穷举出这2n种情况,计算每种情况花费的时间,并选择出时间最短的那一种。

    这种方法一定可以找到最优解,但是单单考虑到任务分配便有2^n种情况,再考虑到每种情况计算时间的过程,复杂度过高,算法无效。


    动态规划解法

    简单的动态规划思路

    上面的穷举法的思想是将任务当作自变量,完成时间当作因变量,复杂度下限为 O(2^n)。

    但是,我们可以注意到:完成任务最慢的情况,是把所有任务都交给一台机器完成,另一台机器全程闲置。但是,即使在这种情况下,也是可以在有限时间内完成任务的。设sum_a=a[0]+a[1]+···+a[n-1]sum_b=b[0]+b[1]+···+b[n],设max_sum_ab=max(sum_a,sum_b),易知,待求的最短时间一定不超过max_sum_ab。

    由以上分析,我们可以引出动态规划解法的思路。设布尔量p[i][j][k]表示前k个作业是否可以在处理机A用时不超过i且处理机B用时不超过j时间内完成。由上述分析,我们可以知道:当i>=sum_a,或者j>=sum_b时,p[i][j][k]一定为真。那么我们可以使用穷举法,将机器A、B花费的时间分别从0枚举至sum_a和sum_b,对于每种情况,都求出p的bool值,再从中选择出最短时间即可。

    这里对p的定义进行一些补充。已经清楚的朋友可以跳过下面这一段。

    • p[i][j][k]是一个bool值,其真假表示a机器花费i时间、b机器花费j时间的前提下,是否可以完成k个任务。我们这里假设任务都是按顺序处理。也就是说,假设机器A花费时间i、机器B花费时间j,若可以在此时间内完成至任务k,那么p[i][j][k]=true,否则为false。

      举个例子理解一下:

    任务1任务2
    A机器花费时间34
    B机器花费时间28
    • 假设一共有两个任务,花费时间如上。由以上表格可知:p[7][0][2]=true。因为,若把所有任务都给A机器,那么A机器时间消耗为7,B机器时间消耗为0,完成任务数为2,即p[7][0][2]=true。
    • 同时,p[4][2][2]=true。把任务1给B,任务2给A,恰好A机器时间花费为4,B机器时间花费为2,此时两个任务都可以完成。
    • 以此类推,p[3][2][2]=false,因为当机器A花费时间不超过3并且B不超过2时,显然是无法完成两个任务的。

    递推关系

    到这里,动态规划的基本思想已经解释清楚了。接下来的关键就是如何将p[0..sum_a][0..sum_b][0..n]全部求出来。

    实际上,第k个任务和第k-1个任务有密不可分的关系。假设p[0..sum_a][0..sum_b][0..k-1]已经全部求解完毕。那么完成第k件任务有两个选择:分配给A机器,或者B机器。假设A花费i时间、B花费j时间,可以完成任务k-1,那么A花费i+ak时间、B花费j时间,一定可以完成任务k。同样的,若A花费i时间、B花费j+bk时间,也一定可以完成任务k。因为这就相当于将k分别交给A或者B完成。

    将上面的关系写成以p表示的形式,即p[i][j][k]=p[i-ak][j][k-1] || p[i][j-bk][k-1]。解释如下:p[i][j][k]=true,表示完成k个任务,a、b机器使用的时间分别不超过i、j。那么我们可以推知:p[i-ak][j][k-1]p[i][j-bk][k-1]中必有一个为true。因为:在完成第k-1个任务后,第k个任务要不是A机器处理,要不是B机器处理,分别对应着 p[i-ak+ak][j][k-1+1]p[i][j-bk+bk][k-1+1]。所以,p[i][j][k]=p[i-ak][j][k-1] || p[i][j-bk][k-1]

    最后,求得所有p的值后,我们找到所有值为true的p,选出min(max(i,j))即为问题的解。先取max,是因为最终结果取决于A和B中花费时间较长的那一个。再取min,是因为我们要在所有能够完成任务的(i,j)组合中寻出最小值。

    主要代码如下:

    const int get_min_time_dyna_3d()	//使用三维数组
    {
    	·····   //这里是部分初始化操作
    
    	for (k = 1; k <= n; k++) {  //每次循环,安排一件任务
    		for (i = 0; i <= mn; i++) { //a机器的时间从0~mn逐步尝试
    			for (j = 0; j <= mn; j++) {
    				if (i - a[k - 1] >= 0)  //若当前任务可以由a机器在i时间内完成
    					p[i][j][k] = p[i - a[k - 1]][j][k - 1];
    				if (j - b[k - 1] >= 0)  //若当前任务可以由b机器在j时间内完成
    					p[i][j][k] = p[i][j][k] || p[i][j - b[k - 1]][k - 1];
    			}
    		}
    	}
    
    	····	//遍历p,在p为true的前提下选出 ret=min(max(i,j))
    
    	return ret;
    
    }
    

    算法复杂度分析

    上述算法的时间复杂性主要在三重循环上。时间复杂度为 O(m2n3)。

    同时,该算法空间复杂度也较高,主要空间花费在p数组上,复杂度为 O(m2n3)。

    虽然复杂度高,但是相比穷举法的 O(2n) 已经降下了很多。


    算法改进

    上述算法使用了三维数组,空间复杂度高。我们考虑可否对其进行优化:

    可以想象:当i和k不变时,p[i][j][k]的bool值对于j有一个临界值j0。当j<j0时,p[i][j][k]=false;当j>=j0时,p[i][j][k]=true

    所以,我们可以将三维数组改为二维数组 p[i][k]=int,表示a机器花费不超过i时间且能够完成k个任务时,b机器花费时间的最小值。也就是上面说到的j0。

    算法改进的思想已经介绍完毕。那么,要怎么求出p[0..sum_a][0..n]的值呢?我们还是可以这样考虑:假设p[0..sum_a][0..k-1]已经全部求解完毕(注意这里的p[i][k]的值表示的是B机器花费的最少时间)。那么完成第k件任务有两个选择:分配给A机器,或者B机器。若我们把任务k分配给A机器,那么p[i][k]=p[i-ak][k-1],因为这个任务是由A完成的,所以B花费的最短时间同上次没有变化。若分配给B机器,那么p[i][k]=p[i][k-1]+bk,将B花费的最短时间加上了完成任务k的时间。

    究竟是选A还是选B呢?我们的目的是在p中存储B花费时间的最小值。这样的话,递推方程就变为:p[i][k]=min(p[i-ak][k-1],p[i][k-1]+bk)

    改进后的代码如下:

    const int get_min_time_dyna_2d()
    {
    	···		//初始化操作。注意需要将p数组全部置0
    
    	for (k = 1, sum_a = 0; k <= n; k++) {
    		//k表示当前完成到第几个任务。作下标使用需要-1
    		sum_a += a[k - 1];	//每次迭代,A机器最长时间不超过a1+a2+···+ak
    		for (i = 0; i < sum_a; i++) {	//i=sum_a时不用算,因为p一定是0
    			p[i][k] = p[i][k - 1] + b[k - 1];
    			if (i >= a[k - 1])
    				p[i][k] = p[i][k] < p[i - a[k - 1]][k - 1] ? 
    						p[i][k] : p[i - a[k - 1]][k - 1];
    		}
    	}
    
    	for (i = 0, ret = INTMAX; i <= sum_a; i++) {
    		//遍历p,选出 ret=min(max(i,j))
    		int max_ij = i > p[i] ? i : p[i];
    		if (max_ij < ret)
    			ret = max_ij;
    	}
    	····	//内存释放等操作
    
    	return ret;
    }
    

    再次改进算法

    观察上述改进后的算法可知,虽然p数组记录了 p[0..sum_a][0..n],但是最终使用到的仅有 p[0..sum_a][n]。因此,我们可以进一步改进算法,使用一维数组p[i]=j来记录完成所有任务且A机器花费不超过i时间的情况下,B机器花费时间的最小值。

    算法的思想与二维数组完全一致,但是由于p数组的值不断更新,循环的前期其实p记录的并不是完成所有任务的时间,所以代码可读性变差。这里不再对其进行解释,仅将代码附在文末。


    代码

    #include <iostream>
    #include<string.h>
    using namespace std;
    
    const int INTMAX = 0x7fffffff;
    
    int n;
    int* a, * b;
    
    const int get_min_time_dyna_1d()
    {
    	const int n = ::n;		//防止求解过程中修改n、a、b
    	const int* a = ::a;
    	const int* b = ::b;
    
    	int i, k;
    	int* p;	//p[i]=j表示所有任务由a完成不超过i时间,由b完成不超过j时间
    	int ret;
    
    	int sum_a = 0, sum_b = 0;	//存储任务完全由a/b机器完成所需要花费的时间
    	for (i = 0; i < n; i++) {
    		sum_a += a[i];
    		sum_b += b[i];
    	}
    
    	try {
    		p = new int[sum_a + 1];
    	}
    	catch (const std::exception& e) {
    		cerr << "内存申请失败!" << e.what() << endl;
    		return -1;
    	}
    
    	for (i = 0; i <= sum_a; i++)
    		p[i] = 0;		//初始化,假设任务全由a完成
    
    	for (k = 0; k < n; k++) {	//每次循环完成一件任务
    		for (i = sum_a; i >= 0; i--) {	//初始化时,任务全由a完成
    			p[i] = p[i] + b[k];	//初始化,把任务k派给b机器
    			if (i >= a[k])	//如果a机器在i时间也可以完成任务k
    				p[i] = p[i] < p[i - a[k]] ? p[i] : p[i - a[k]];
    		}
    	}
    
    	for (i = 0, ret = INTMAX; i <= sum_a; i++) {
    		int temp = i > p[i] ? i : p[i];
    		if (temp < ret)
    			ret = temp;
    	}
    
    	delete[]p;
    	return ret;
    }
    
    const int get_min_time_dyna_2d()
    {
    	const int n = ::n;
    	const int* a = ::a;
    	const int* b = ::b;
    
    	int i, k;
    	int** p;	//p[i]=j表示所有任务由a完成不超过i时间,由b完成不超过j时间
    	int ret;
    
    	int sum_a = 0;	//存储任务完全由a机器完成所需要花费的时间
    	for (i = 0; i < n; i++)
    		sum_a += a[i];
    
    	const int total_sum_a = sum_a;	//记录a的任务时间总和
    
    	try {
    		p = new int* [total_sum_a + 1];
    		for (i = 0; i <= total_sum_a; i++) {
    			p[i] = new int[n + 1];
    			memset(p[i], 0, (n + 1) * sizeof(int));	//初始全部置0
    		}
    	}
    	catch (const std::exception& e) {
    		cerr << "内存申请失败!" << e.what() << endl;
    		return -1;
    	}
    
    	for (k = 1, sum_a = 0; k <= n; k++) {
    		//k表示当前完成到第几个任务。作下标使用需要-1
    		sum_a += a[k - 1];
    
    		for (i = 0; i < sum_a; i++) {	//i=sum_a时不用算,因为p一定是0
    			p[i][k] = p[i][k - 1] + b[k - 1];
    			if (i >= a[k - 1])
    				p[i][k] = p[i][k] < p[i - a[k - 1]][k - 1] ? p[i][k] : p[i - a[k - 1]][k - 1];
    		}
    	}
    
    	for (i = 0, ret = INTMAX; i <= total_sum_a; i++) {
    		int max_ij = i > p[i][n] ? i : p[i][n];
    		if (max_ij < ret)
    			ret = max_ij;
    	}
    
    	for (i = 0; i <= total_sum_a; i++)
    		delete[]p[i];
    	delete[]p;
    	return ret;
    }
    
    const int get_min_time_dyna_3d()
    {
    	const int n = ::n;
    	const int* a = ::a;
    	const int* b = ::b;
    
    	int i, j, k;
    	bool*** p;
    
    	int sum_a = 0, sum_b = 0;	//存储任务完全由a/b机器完成所需要花费的时间
    	for (i = 0; i < n; i++) {
    		sum_a += a[i];
    		sum_b += b[i];
    	}
    
    	int ret;
    
    	try {
    		p = new bool** [sum_a + 1];
    		for (i = 0; i <= sum_a; i++)
    			p[i] = new bool* [sum_b + 1];
    		for (i = 0; i <= sum_a; i++)
    			for (j = 0; j <= sum_b; j++)
    				p[i][j] = new bool[n + 1];
    	}
    	catch (const std::exception& e) {
    		cerr << "内存申请失败!" << e.what() << endl;
    		return -1;
    	}
    
    	for (i = 0; i <= sum_a; i++) {
    		for (j = 0; j <= sum_b; j++) {
    			p[i][j][0] = true;
    			for (k = 1; k <= n; k++)
    				p[i][j][k] = false;
    		}
    	}
    
    	for (k = 1; k <= n; k++) {
    		for (i = 0; i <= sum_a; i++) {
    			for (j = 0; j <= sum_b; 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];
    			}
    		}
    	}
    
    	for (i = 0, ret = INTMAX; i <= sum_a; i++) {
    		for (j = 0; j <= sum_b; j++) {
    			if (p[i][j][n]) {
    				int tmp = (i > j) ? i : j;
    				if (tmp < ret)
    					ret = tmp;
    			}
    		}
    	}
    
    	for (i = 0; i <= sum_a; i++) {
    		for (j = 0; j <= sum_b; j++)
    			delete[] p[i][j];
    		delete[]p[i];
    	}
    	delete[]p;
    
    	return ret;
    
    }
    
    int main()
    {
    	cin >> n;
    
    	try {
    		a = new int[n];
    		b = new int[n];
    	}
    	catch (const std::exception& e) {
    		cerr << "内存申请失败!" << e.what() << endl;
    		return -1;
    	}
    
    	for (int i = 0; i < n; i++)
    		cin >> a[i];
    	for (int i = 0; i < n; i++)
    		cin >> b[i];
    
    	cout << get_min_time_dyna_1d() << endl;
    
    	delete[]a;
    	delete[]b;
    
    	return 0;
    }
    
    更多相关内容
  • 全都是自己写的,都能跑出来 实打实写的哦~ 仅供参考 最重要的还是自己理解 用动态规划算法设计独立任务最优调度问题解决方案并实现,并分析算法复杂性。 预览地址:
  • 实现3-1独立任务最优调度问题.cpp
  • 3-1独立任务最优调度问题 间a,若由机器B来处理,则需要时间b。由于各作业的特点和机器的性能关系,很可能对于某些i,有a≥b,而对于某些j,ji,有a。既不能将一个作业分开由2台机器处理,也没有一台机器能同时处理2个作业...
  • 《计算机算法设计与分析(王晓东)》课后3.1 已经编译通过,完全正确。 独立任务最优调度问题
  • 独立任务最优调度室算法课上经典的题目,这是本人写的一种新的算法,算法复杂度为O(n*max*max)
  • 独立任务最优调度问题

    独立任务最优调度问题

    image-20220411192316268

    采取动态规划的算法

    d p [ k ] [ i ] [ j ] 代 表 前 k 个 作 业 可 以 在 A 用 时 不 超 过 i , B 用 时 不 超 过 j 的 时 间 内 完 成 dp[k][i][j]代表前k个作业可以在A用时不超过i,B用时不超过j的时间内完成 dp[k][i][j]kAiBj

    则有 d p [ k ] [ i ] [ j ] = d p [ k − 1 ] [ i − a k ] [ j ] ∣ d p [ k − 1 ] [ i ] [ j − b k ] dp[k][i][j]=dp[k-1][i-a_k][j]|dp[k-1][i][j-b_k] dp[k][i][j]=dp[k1][iak][j]dp[k1][i][jbk]

    求出其中最大的耗时即 m a x C o s t = m a x ( m a x ( a i ) , m a x ( b i ) ) maxCost=max({max({a_i}),max({b_i}))} maxCost=max(max(ai),max(bi))

    需要开辟的数组空间为$ (maxCostk)(maxCost*k)*k$

    只需要找到使得 d p [ k ] [ i ] [ j ] = = 1 dp[k][i][j]==1 dp[k][i][j]==1成立的 m a x ( i , j ) max(i,j) max(i,j)的最小值即可

    而对于每个作业,只需要对其在A和B上分别赋值即可.而显然 i i i需要大于等于 a k a_k ak, j j j需要大于等于 b k b_k bk

    代码如下:

    # -*- coding: utf-8 -*-
    """
    Created on Mon Apr 11 11:00:46 2022
    
    @author: skyoung
    """
    
    ## 先读入数据
    import re
    fin=open('input.txt','r')
    n=int(fin.readline().strip('\n').strip(' '))
    dataA=(fin.readline().strip())
    dataA=re.findall("\d+",dataA)
    dataB=(fin.readline().strip())
    dataB=re.findall("\d+",dataB)
    dataA=[int(x) for x in dataA]
    dataB=[int(x) for x in dataB]
    fin.close() 
    # 处理完毕,开始进行分类处理
    
    
    #先寻找一下最大耗时
    maxCost=max(max(dataA),max(dataB))*n
    
    dp=[[[0]*(maxCost+1) for _ in range(maxCost+1)] for _ in range(n+1)]
    
    for i in range(maxCost):
        for j in range(maxCost):
                       dp[0][i][j]=1 #从第一件开始
                       
    
    for k in range(1,n+1):
        for j in range(maxCost):
            i=maxCost
            while i>=dataA[k-1]:
                dp[k][i][j]=dp[k-1][i-dataA[k-1]][j]
                i-=1
        for i in range(0,maxCost):
            j=maxCost
            while j>=dataB[k-1]:
                dp[k][i][j]=dp[k-1][i][j-dataB[k-1]]
                j-=1
                
    res=123456789#开大一点
    for i in range(maxCost):
        for j in range(maxCost):
            if dp[n][i][j]==1:
                temp=max(i,j)
                if temp<res:
                    res=temp
    print("the answer is ",res)
    

    空间复杂度为 O ( n ∗ n ∗ m a x C o s t ) O(n*n*maxCost) O(nnmaxCost)

    时间复杂度为 O ( n ∗ n ∗ m a x C o s t ∗ m a x C o s t ∗ n ) O(n*n*maxCost*maxCost*n) O(nnmaxCostmaxCostn)

    展开全文
  • 独立任务最优调度问题+算法设计

    热门讨论 2011-05-16 13:34:40
    问题描述:独立任务最优调度,又称双机调度问题:用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时所需要的时间是a[i],若由机器B来处理,则所需要的时间是b[i]。现在要求每个作业只能由一台机器处理,每台...
  • 思路: A机器第i个作业需要的处理时间记为a[i]; B机器第i个作业需要的处理时间记为b[i]; F[i][j]表示完成i个作业机器A花费j时间的条件下机器B所费时间的最小值 假设前i-1个作业已经被处理了,第i件作业有两种...

    思路:

    A机器第i个作业需要的处理时间记为a[i];

    B机器第i个作业需要的处理时间记为b[i];

    F[i][j]表示完成i个作业机器A花费j时间的条件下机器B所费时间的最小值

    假设前i-1个作业已经被处理了,第i件作业有两种处理方式:

    1. 机器A处理:则B时间为F[i-1][j-a[i]];即B为处理上一个作业的时间
    2. 机器B处理:则B时间为F[i-1][j]+b[i];

    其中有特殊情况:如果j<a[i],则不可能由A完成,只能由B完成,即为B处理情况

    得出:F[i][j]=min{F[i-1][j]+b[i],F[i-1][j-a[i]]}

    算法思路:

    确立B最小时间时,取其中最小值;

    计算作业完成时间时,取最大值(因为A,B都完工才算处理完成作业);

    再从这些最大值中比较选出最小值

    代码:

    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;;
    int a[201],b[201];
    int f[201][10001];
    int sum=0;
    int main()
    {
        ifstream fin("sched10.in",ios::in);
        ofstream fout("answer10.txt");
        int n;
        fin>>n;
        int minx=99999;
        memset(f,0,sizeof f);
        for(int i=1;i<=n;i++)
            {
                fin>>a[i];
    //            cout<<a[i]<<endl;
            }
        for(int i=1;i<=n;i++)
            {
                fin>>b[i];
    //            cout<<b[i]<<endl;
            }
        for(int i=1;i<=n;i++)
        {
            sum+=a[i];
            for(int j=0; j<=sum; j++)
            {
                f[i][j]=f[i-1][j]+b[i];
                if(j>=a[i])
                    f[i][j]=min(f[i-1][j]+b[i],f[i-1][j-a[i]]);
                }
        }
        for(int i=0;i<=sum;i++)
            minx=min(minx,max(f[n][i],i));
         fout<<minx;
         cout<<minx;
         fout.close();
         fin.close();
        return 0;
    }
    

    展开全文
  • 算法分析与设计实验报告——独立任务最优调度问题 目录:算法分析与设计实验报告——独立任务最优调度问题一、 实验目的二、实验要求三、 实验原理四、 实验过程(步骤)五、 运行结果六、实验分析与讨论七、实验特色...

    算法分析与设计实验报告——独立任务最优调度问题

    一、 实验目的

    掌握动态规划的基本思想和解决问题的基本步骤,认识动态规划和分治法的联系与区别,对比解决同一问题的两种算法设计策略的时间复杂性。

    二、实验要求

    用c++语言实现用动态规划算法解决独立任务最优调度问题,分析时间复杂性,体会动态规划算法解决问题的基本思路和步骤。

    三、 实验原理

    独立任务最优调度问题具有最优子结构性质。先计算m=max{max{ai},max{bi}},设布尔量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 )

    则最短时间为min{max{i,j}}

    四、 实验过程(步骤)

    见附件一
    实验步骤、特点
    重要源代码(流操作的部分要醒目的提示并注释)

    五、 运行结果

    见附件二

    六、实验分析与讨论

    一开始没有想到用三维数组来解决,没有思路,经过查阅资料才明白了这个问题的动态规划算法。三维数组的创建与释放对我来说也是一个问题。最后都是查找了很多资料才解决的。
    遇到的问题,及解决方案

    七、实验特色与心得

    这次试验掌握了独立任务最优调度问题的动态规划的基本思想和解决问题的基本步骤,充分认识了动态规划和分治法的联系与区别,还分析了此算法的时间复杂度为O(m2n2),再次提高了自己的能力。

    附件一 实验过程(步骤)

    // Created by DZX on 2020/12/3.
    //独立任务最优调度问题
    #include "bits/stdc++.h"
    using namespace std;
    int n, m, mn, MiniTime;
    int *a;
    int *b;
    int ***p;
    void Make3DArray(int ***&x, int rows, int cols, int k) {//创建3维数组
        x = new int **[rows];
        for (int i = 0; i < rows; i++) {
            x[i] = new int *[cols];
            for (int j = 0; j < cols; j++)
                x[i][j] = new int[k];
        }
    }
    void Free3DArray(int ***&x, int rows, int cols, int k) {//释放3维数组
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                free(x[i][j]);
            }
            free(x[i]);
        }
        free(x);
    }
    void init() {//初始化,输入数据创建数组
        cin >> n;
        m = 0;
        a = new int[n];
        b = new int[n];
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] > m)
                m = a[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> b[i];
            if (b[i] > m)
                m = b[i];
        }
        mn = m * n;
        Make3DArray(p, mn + 1, mn + 1, n + 1);
    }
    void dtgh() {//执行动态规划算法
        int i, j, k;
        //初始化三维数组
        for (i = 0; i <= mn; i++) {
            for (j = 0; j <= mn; j++) {
                p[i][j][0] = true;
                for (k = 1; k <= n; k++)
                    p[i][j][k] = false;
            }
        }
        for (k = 1; k <= n; k++) {//执行动态规划递归
            for (i = 0; i <= mn; i++) {
                for (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]);
                }
            }
        }
        for (i = 0, MiniTime = mn; i <= mn; i++) { //计算最优值
            for (j = 0; j <= mn; j++) {
                if (p[i][j][n]) {
                    int tmp = (i > j) ? i : j;
                    if (tmp < MiniTime)
                        MiniTime = tmp;
                }
            }
        }
        cout << "完成全部作业所需最短时间:"<<MiniTime << endl;
    }
    void free() {//释放申请的空间
        Free3DArray(p, mn + 1, mn + 1, n + 1);
        free(a);
        free(b);
    }
    int main() {//主程序
        init();
        dtgh();
        free();
        return 0;
    }
    /*
    6 15
    2 5 7 10 5 2
    3 8 4 11 3 4
     */
    

    附件二 运行结果

    在这里插入图片描述

    展开全文
  • 算法设计与分析——独立任务最优调度问题

    千次阅读 多人点赞 2020-04-05 10:52:01
    独立任务最优调度问题 ★问题描述: 用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai.若由机器B来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些i,有ai≥bi,而对于某些j≠...
  • 题目意思很好理解,需要注意的是虽然一台机器不能同时处理两个任务,但是两台机器可以同时处理两个任务,所以就样例而言,对于第一个任务,可以选择由A或B来做,第二个任务也可以选择A或B,所以就形成了最简单的暴力...
  • 动态规划之独立任务最优调度问题

    千次阅读 2020-05-21 22:32:07
    给出了每个作业在A、B处理机上处理的时间,我们应该找出所有任务全部完成的调度时间。 题目分析 题目要求我们设计一个动态规划算法,计算出完成所有作业所用的最短时间。 根据我们动态规划的基本框架,先找到状态,...
  • 很可能对于某些 i,有 ai>=bi,而对于某些 j,j≠i,有 aj (a1,a2,a3,a4,a5,a6)=(2,5,7,10,5,2) (b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4) 对于给定的 2 台处理机 A 和 B 处理 n 个作业,找出一个最优调度方案,使 2 ...
  • 算法大作业 独立任务最优调度问题 有源码和报告
  • 问题描述: 用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai,若由机器B来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些i,有ai>bi,而对于某些j,j≠i,有aj>bj...
  • 3-1 独立任务最优调度问题(双机调度问题) 问题描述 用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间aiaia_i,若由机器B来处理,则需要时间bibib_i。由于各作业的特点和机器的性能关系,很...
  • 算法实现题3-1独立任务最优调度问题 **问题描述:**用2 台处理机A 和B 处理n 个作业。设第i 个作业交给机器A 处理时需要时间ai,若由机器B 来处理,则需要时间bi。由于各作业的特点和机器的性能关系,很可能对于某些...
  • 用两台处理机A和B处理n个作业。设第i个作业交给A处理需要时间ai,交给B处理需要时间bi。由于各作业的特点和机器的性能关系,ai和bi...测试用例:6(任务数目)2 5 7 10 5 2(机器A处理这些任务的时间)3 8 4 11 3 4(机器...
  • ´问题描述: 用 2 台处理机 A 和 B 处理 n 个作业。设第 i 个作业交给机器 A 处理时需要时间 i a ,若 由机器 B 来处理,则需要时间 i b 。由于各作业的特点和机器的性能关系,很可能对于某些 i, 有 i i a ³ b ,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,854
精华内容 4,341
关键字:

独立任务最优调度问题