-
Notifications
You must be signed in to change notification settings - Fork 0
/
final.cpp
45 lines (42 loc) · 985 Bytes
/
final.cpp
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
const int MAXV=20005;
int path[MAXN][MAXV];
int dp[MAXV];
int sum; //表示所有任务的时间总和
int n; //表示任务总数
int t[MAXN];
int ans[MAXN]; //记录任务被安排在哪台机器上
int main()
{
sum=0;
memset(dp,0,sizeof dp);
memset(path,0,sizeof path);
cin>>n;
for(int i=1;i<=n;i++){
cin>>t[i];
sum+=t[i];
}
int V=sum/2;
for(int i=1;i<=n;i++){
for(int j=V;j>=t[i];j--){
if(dp[j-t[i]]+t[i]>dp[j]){
dp[j]=dp[j-t[i]]+t[i];
path[i][j]=1;
}
}
}
for(int i=n,j=V;i>=1&&j>0;i--){
if(path[i][j]){
ans[i]=1;
j-=t[i];
}
}
cout<<"总加工时间为:";
cout<<max(dp[V],(sum-dp[V]))<<endl;
cout<<"调度方案为:"<<endl;
for(int i=1;i<=n;i++){
cout<<"任务:"<<i<<" "<<"加工机器:"<<ans[i]+1<<endl;
}
}