问题描述：
⽤2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间，若由机器B来处理，则需要时间。由于各作业的特点和机器的性能关系，很可能对于某些i，有，⽽对于某些j,j≠i，有。既不能将⼀个作业分开由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个作业的时间最短。
数据输⼊：
由⽂件提供输⼊数据。⽂件的第1⾏是1个正整数n, 表⽰要处理n个作业。接下来的2⾏中，每⾏有n个正整数，分别表⽰处理机A和B 处理第i个作业需要的处理时间。
结果输出:
将计算出的最短处理时间输出到⽂件中。
输⼊⽂件⽰例输出⽂件⽰例
<
15
6
2 5 7 10 5 2
3 8
4 11 3 4
问题分析：
对于这个问题，我们可以考虑，当完成第k个任务时，有两种可能：xujie
⼀是A处理机完成了第k个任务，那么B处理机完成k个任务的最短时间就与B处理机完成k-1个任务所需的最短时间是相同的
⼆是B处理机完成了第k个任务，那么B处理机完成k个任务的最短时间就等于B处理机完成k-1个任务的最短时间加上B处理机完成第k个任务所需要的时间
设F[k][x]表⽰完成第k个任务时A耗费的时间为x的情况下B所花费的最短时间，其中0<=k <= n， 0<=x<= Σai，那么，状态转移⽅程为F[k] [x]=minF[k−1][x−ak],F[k−1][x]+bk 处理好特殊情况（如x⼩于0时）开始填表即可。
最终的结果即是完成n个任务时A和B所需时间的较⼤值，即max(F[n][x], x).
算法实现：
1 #include<iostream>
2 #include<fstream>
3 #include<string.h>
4using namespace std;
5
6int get_result(int a[],int b[],int n)
7 {
8if(n==1)
9return min(a[0], b[0]);
10int sum = 0,result = 10000;
11for(int i=0;i<n;i++)
12 {
13 sum+=a[i];
14 }
15int f[n][sum+1];
16//初始化f（B处理⽤的时间）的各个元素为0
17 memset(f, 0, sizeof(f));
18
19//初始化完成第⼀个任务时的情况
20for(int x=0;x<a[0];x++)
21 {
22 f[0][x]=b[0];
23 }丫髻山碧霞元君祠遗址
24 f[0][a[0]]=0;
25
26//动态规划过程
27 sum=a[0];
28for(int k=1;k<n;k++)
29 {
30 sum+=a[k];
31for(int x=0;x<=sum;x++)
32 {
33if(x<a[k])
34 {
35 f[k][x]=f[k-1][x]+b[k];
36 }
37else
38 {
39 f[k][x]=min(f[k-1][x-a[k]],f[k-1][x]+b[k]);
40 }
41if(k==n-1)
42 {
43int val = max(x,f[k][x]);
44if(val<result)
45 result = val;
46 }
47 }
48 }
49return result;
鞍钢一公司8人被脱硫灰埋压50 }
51
52int main()
53 {
54int n;
55 ifstream ifs;//创建⽂件流
56 ofstream ofs;
57 ifs.open("");
58 ofs.open("");
59if(!ifs.is_open()||!ofs.is_open())
60 {
61 cout<<"open failed!"<<endl;
62return0;
63 }
64 ifs>>n;
65int a[n+1],b[n+1];
66for(int i=0;i<n;i++)
67 {
68 ifs>>a[i];
69 }
70for(int i=0;i<n;i++)
71 {
72 ifs>>b[i];
73 }
74int result=get_result(a,b,n);
75 cout<<result<<endl;
76 ofs<<result;
77 ifs.close();
78 ofs.close();
79return0;
80
81 }
运⾏结果：
算法分析：
在get_result函数中，有两个嵌套for循环，时间复杂度为O(n*sum)，所以时间复杂度为O(n2)。
经验归纳：
动态规划解题的⼀般思路：
1. 将原问题分解为⼦问题
把原问题分解为若⼲个⼦问题，⼦问题和原问题形式相同或类似，只不过规模变⼩了。⼦问题都解决，原问题即解决。
⼦问题的解⼀旦求出就会被保存，所以每个⼦问题只需求解⼀次。
2.确定状态
在⽤动态规划解题时，我们往往将和⼦问题相关的各个变量的⼀组取值，称之为⼀个“状态”。⼀个“状态”对应于⼀个或多个⼦问题，所谓某个“状态”下的“值”，就是这个“状态”所对应的⼦问题的解。
热辐射
所有“状态”的集合，构成问题的“状态空间”。“状态空间”的⼤⼩，与⽤动态规划解决问题的时间复杂度直接相关。在数字三⾓形的例⼦⾥，⼀共有N×(N+1)/2个数字，所以这个问题的状态空间⾥⼀共就有N×(N+1)/2个状态。
整个问题的时间复杂度是状态数⽬乘以计算每个状态所需时间。在数字三⾓形⾥每个“状态”只需要经过⼀次，且在每个状态上作计算所花的时间都是和N⽆关的常数。
3.确定⼀些初始状态（边界状态）的值
noetv
4. 确定状态转移⽅程
cctv电视剧英汇定义出什么是“状态”，以及在该“状态”下的“值”后，就要出不同的状态之间如何迁移――即如何从⼀个或多个“值”已知的 “状态”，求出另⼀个“状态”的“值”(递推型)。状态的迁移可以⽤递推公式表⽰，此递推公式也可被称作“状态转移⽅程”。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议