问题描述:
用 $2$ 台处理机 $A$ 和 $B$ 处理 $n$ 个作业。设第 $i$ 个作业交给机器 $A$ 处理时需要时间 $a_i$ ,若 由机器 $B$ 来处理,则需要时间 bi 。
由于各作业的特点和机器的性能关系,很可能对于某些 $i$, 有 $a_i\leq b_i$ ,而对于某些 $j$, $j \neq i$,有 ${a_j}<{b_j}$ 。既不能将一个作业分开由 $2$ 台机器处理,也 没有一台机器能同时处理 $2$ 个作业。设计一个动态规划算法,使得这 $2$ 台机器处理完这 $n$ 个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。研究一个实例: ( $a_1,a_2,a_3,a_4,a_5,a_6$ ) = (2, 5, 7, 10, 5, 2); ( $b_1,b_2,b_3,b_4,b_5,b_6$ ) = (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 中。
输入文件示例 输出文件示例
1 2 3
| 6 2 5 7 10 5 2 3 8 4 11 3 4
|
output
解析:
首先看完题脑子🧠里就会出现一个暴力的 $O(2^n)$ 的思路,这题的 $n\le 200$ ,暴力的能跑 $n \le 30$ 的都不错了,虽然知道肯定会会超时,但还是随手写了一下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| #include <iostream> #include <cstdio> #include <climits> using namespace std; const int maxn = 200 + 10; int a[maxn], b[maxn]; int ans = INT_MAX, n; void dfs(int idx, int sum1, int sum2){ if(idx==n){ ans = min(ans, max(sum1, sum2)); return ; } dfs(idx+1, sum1 + a[idx], sum2 + 0); dfs(idx+1, sum1 + 0, sum2 + b[idx]); } int main(){ while(cin >> n){ ans = INT_MAX; for(int i=0; i<n; i++) cin >> a[i]; for(int i=0; i<n; i++) cin >> b[i]; dfs(0, 0, 0); cout << ans << endl; } return 0; }
|
接下来就只能推状态转移方程了。
设 $dp[i][j]$ 表示前 $i$ 个作业 $A$ 机器用了 $j$ 时间的条件下 $B$ 机器最少花费的时间。
首先设 $sum=\sum_{i=1}^{n}{a_i}$ ,然后令 $j\in[1,sum]$ 。
则:
$$
dp[i][j]=min(dp[i-1][j-a[i]],dp[i-1][j]+b[i])
$$
解释一下上面两个状态:
- $dp[i-1][j-a[i]]$ : 第 $i$ 个任务交给 $A$ 机器,所以前 $i-1$ 个任务 $A$ 机器花费 $j-a[i]$ 。
- $dp[i-1][j]+b[i]$ : 第 $i$ 个任务交给 $B$ 机器,所以前 $i-1$ 个任务 $A$ 机器花费的时间就是 $j$ 。
所以结果就是 $max(j,dp[n][j])|j\in[1,sum]$ 的最小值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| #include <iostream> #include <cstdio> #include <climits> #include <cstring> using namespace std; const int maxn = 200 + 10; const int MAX = 1e4; int a[maxn], b[maxn]; int dp[maxn][MAX]; int ans, n; int main(){ while(cin >> n){ int sum = 0; for(int i=1; i<=n; i++) cin >> a[i], sum += a[i]; for(int i=1; i<=n; i++) cin >> b[i]; memset(dp, 0x3f3f3f3f, sizeof(dp)); dp[0][0] = 0; for(int i=1; i<=n; i++){ for(int j=0; j<=sum; j++){ if(j>=a[i]) dp[i][j] = min(dp[i][j], dp[i-1][j-a[i]]); dp[i][j] = min(dp[i][j], dp[i-1][j] + b[i]); } } ans = dp[n][0]; for(int j=1; j<=sum; j++){ ans = min(ans, max(dp[n][j], j)); } cout << ans << endl; } return 0; }
|