一、问题描述:
用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个作业的时间最短。
输入：
6
2 5 7 10 5 2
3 8 4 11 3 4输出：
15二、思路分析
题目要求使用动态规划的算法，先给出状态转移方程：
其中表示到第i个作业，A机器花费时间为j的情况下，B机器处理的最短时间。
我们分为两种情况：
1、A处理机完成了第i个任务，那么B处理机完成k个任务的最短时间就与B处理机完成i-1个任务所需的最短时间是相同的，即
2、B处理机完成了第i个任务，那么B处理机完成i个任务的最短时间就等于B处理机完成i-1个任务的最短时间加上B处理机完成第i个任务所需要的时间，即
文章来源：https://www.toymoban.com/news/detail-513465.html
我们完成作业的最短时间是由A机器完成时间和B机器完成时间中较大的那一者来决定，因为一项作业的真正完工需要两个都完成才算完成。 所以在最终计算完成时间时，我们要取A、B完成时间的最大值，再根据每个不同j的取值（即分配给A机器花费时间j的不同情况下）循环遍历查找最小的那个，代码中为x代替j。文章来源地址https://www.toymoban.com/news/detail-513465.html
三、代码
#include <bits/stdc++.h>
#define MAXN 1005
using namespace std;
int a[MAXN];//机器A处理各作业的时间
int b[MAXN];//机器B处理各作业的时间
int F[MAXN][MAXN];
int time_[MAXN];//处理作业k所需要的最短时间
int n;
int dp() {
int sumA = a[1];
//k = 1的情况
for(int x = 0; x < a[1]; x++) { //分配给A的时间小于A处理第一个作业所需时间，给B
F[1][x] = b[1];
}
F[1][a[1]] = min(b[1],a[1]);//正好够A就看谁小
//初始化
for(int i = 2; i <= n; i++) {
for(int j = 0; j <= n; j++) {
F[i][j] = INT_MAX;
}
}
//k >= 2的情况
for(int k = 2; k <= n; k++) {
sumA += a[k];
time_[k] = INT_MAX;
for(int x = 0; x <= sumA; x++) {
if(x < a[k]) {
F[k][x] = F[k-1][x] + b[k];
} else {
F[k][x] = min(F[k-1][x] + b[k], F[k-1][x-a[k]]);
}
time_[k] = min(time_[k],max(x,F[k][x]));
//max(x,F[k][x])表示前k个作业机器A花费x分钟，B机器花费F[k][x]分钟情况下，最迟完工时间
}
}
return time_[n];
}
int main() {
printf("请输入作业数量：");
scanf("%d",&n);
printf("请输入机器A处理每个作业的时间：");
for(int i = 1; i <= n; i++) {
scanf("%d",&a[i]);
}
printf("请输入机器B处理每个作业的时间：");
for(int i = 1; i <= n; i++) {
scanf("%d",&b[i]);
}
printf("总的最少处理时间为：%d\n",dp());
return 0;
}
到了这里，关于【算法设计与分析】C++独立任务最优调度问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
