问题描述:
用 $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;
}
|