´问题描述： 用 2 台处理机 A 和 B 处理 n 个作业。设第 i 个作业交给机器 A 处理时需要时间 i a ，若 由机器 B 来处理，则需要时间 i b 。由于各作业的特点和机器的性能关系，很可能对于某些 i， 有 i i a ³ b ，而对于某些 j,j≠i，有a j < 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 个作业的时间最短。 ´数据输入： 由文件 input.txt 提供输入数据。文件的第 1 行是 1 个正整数 n, 表示要处理 n 个作业。 接下来的 2 行中，每行有 n 个正整数，分别表示处理机 A 和 B 处理第 i 个作业需要的处理时 间。 ´结果输出: 程序运行结束时，将计算出的最短处理时间输出到文件 output.txt 中。 输入文件示例 输出文件示例 input.txt output.txt 6 2 5 7 10 5 2 3 8 4 11 3 4 15
【题解】
设f[i][j]表示前i个作业A机器用了j时间的条件下B最少花费的时间 f[i][j] = min(f[i-1][j-a[i]],f[i-1][j]+b[i]);//给A做或给B做
【代码】
/* 设f[i][j]表示前i个作业A机器用了j时间的条件下B最少花费的时间 f[i][j] = min(f[i-1][j-a[i]],f[i-1][j]+b[i]);//给A做或给B做 */ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 200; const int M = 1e4; int f[N+10][M+10]; int n,a[N+10],b[N+10]; int main(){ freopen("C://Users//Administrator//Desktop//测试数据//ch3//prog31//test//sched10.in","r",stdin); scanf("%d",&n); for (int i = 1;i <= n;i++) scanf("%d",&a[i]); for (int i = 1;i <= n;i++) scanf("%d",&b[i]); memset(f,0x3f3f3f3f,sizeof f); f[0][0] = 0; for (int i = 1;i <= n;i++) for (int j = 0;j <= M;j++){ if (j>=a[i]) f[i][j] = min(f[i][j],f[i-1][j-a[i]]); f[i][j] = min(f[i][j],f[i-1][j]+b[i]); } int ans = f[n][0]; for (int j = 1;j <= M;j++) ans = min(ans,max(f[n][j],j)); printf("%d\n",ans); return 0; }