UC知道这题动态规划该怎么做？给个思路或递推式也好啊！
来源：百度知道 编辑：UC知道 时间：2024/07/08 18:22:15
描述
有n个任务需要依次运行，第i个任务运行时需要占R[i]的空间，运行完成后仍然残留O[i]的空间（ O[i]<R[i]）。现在需要合理安排这些任务，使得运行完这些任务的需要的空间最小。
例如说，有两个任务，R[1]=10，O[1]=5，R[2]=8，O[2]=6。
如果先运行第1个任务，再运行第2个任务，则总共最多需要13的空间；
如果先运行第2个任务，再运行第1个任务，则总共最多需要16的空间；
因此选择第一种方式，使得占用空间最小。
输入
每组数据第一行为任务数 n （n <= 30），接下来的 n 行分别是对应的 R[i] O[i]。
输入以 0 结尾。
输出
对每组数据，输出所需的内存。
样例输入
2
10 5
8 6
5
5 5
4 4
3 3
2 2
1 1
0
样例输出
13
15
有n个任务需要依次运行，第i个任务运行时需要占R[i]的空间，运行完成后仍然残留O[i]的空间（ O[i]<R[i]）。现在需要合理安排这些任务，使得运行完这些任务的需要的空间最小。
例如说，有两个任务，R[1]=10，O[1]=5，R[2]=8，O[2]=6。
如果先运行第1个任务，再运行第2个任务，则总共最多需要13的空间；
如果先运行第2个任务，再运行第1个任务，则总共最多需要16的空间；
因此选择第一种方式，使得占用空间最小。
输入
每组数据第一行为任务数 n （n <= 30），接下来的 n 行分别是对应的 R[i] O[i]。
输入以 0 结尾。
输出
对每组数据，输出所需的内存。
样例输入
2
10 5
8 6
5
5 5
4 4
3 3
2 2
1 1
0
样例输出
13
15
根据你的描述，设Wi=Ri-Oi。只有两个任务t1，t2时，需要空间为V，需要最小空间实际为Vm
设先执行t1再执行t2表示为t1->t2,先执行t2再执行t1表示为t2->t1
则当t1->t2时，有V1=R2-R1+2O1；当t2->t1时，V2=R1-R2+2O2。
那么
V(t1->t2)=Vm(t1->t2)=min{V1,V2}
有了以上定义，能证明：
对于任意的整数0<i<n，若V(ti->t(i+1)) =Vm(ti->t(i+1))，则
任务链满足t1->t2->...->ti->...tn时，有结论：
V(t1->t2...->tn)=Vmin(t1->t2..->tn)
这个结论是我证明就不贴过程了。
一句话就是，一个任务链中，任意相邻的两个任务当前的执行顺序，满足需要空间最小，那么整个任务链按当前顺序执行满足需求空间最小。
所以算法的设计是这样的：
1）对于输入的原始任务顺序，从第一个开始，设计一个指针p指向第一个任务。并设置一个计数器x，初始值为1，设一个变量x初始值n
2）p指向i时与后面的相邻一个任务i+1计算最小空间
3）调整最小空间时的任务顺序。即按照上面的计算，原来是t1->t2，计算后发现V(t1->t2)>V(t2->t1)，则交换t1和t2，否则不交换
4）调整后，p指向下一个任务。若p指向第x个任务，x<c，返回2
5）若c>0,若x=c，则c--，x=1。跳到2)
6) 若c=0.结束任务排序，计算最小空间
这个排序方法类似沉降排序或者冒泡排序，对任意两个任务排序结果是两个任务总需求空间较小。所有的任务排序完毕，满足我上面给出的证明条件。
这时按照这个顺序做任务，所需空间最小。
最小空间是，Vmin=O1+O2+...+On-1+Rn