动态规划的应用-资源分配问题

S1
7
X1
12
3
4
P1(x1)
44
5
8
F2+ p1 21 19
17 18
f1(s1)
21
X1*
1
• 当k=2时;
f2(s2) = max [p2(x2)+ f3(s3) ]
1< x2 < s2 3< s2< 6 计算结果:
S2 X2 p2(x2) F3+ p2 f2(s2) X2*
34 1 12 3 35 10 12 12 10 12 1 1或2
f（k* sk ) max{ fk (sk , xk )}
xk 1,2,3...,sk
4
xi sk
ik
xi大于等于1且为整数
将递推关系写出即是
f
* k
(
sk
)
xk
max
1, 2 ,..., sk
{Pk
(
xk
)
f
* k 1
(
sk
xk )}
f（5* s5）＝0
k 1,2,3
当k=4时;
f4(s4) = max [p4(x4)]
S3 X3 p3(x3) F3+ p3 f3(s3) X3*
23 1 12 5 56 7 98 79 11
4 123 568 12 10 10 12 1
5 1 2 34 5 6 88 13 13 12 10 13 1或2
• 当k=1时;
f1(s1) = max [p1(x1)+ f2(s2) ]
1< x1< s1 s1=7 计算结果:
5 123 35 6 15 14 13 15 1

课程 1 学分 复习天数
234
1
4 35 2
2
54 5 6
3
4
4
5 68 7
8 7 88
解：这个问题要求作出4个相应关联的决策，即应分配多 少天给每门考试科目。因此，即使这里没有固定的次序， 这四门考试科目可以看成动态规划模型中的四个阶段。 阶段：k＝1，2，3，4。考试科目 决策变量：x（k k＝1，2，3，4）是分配到阶段（考试科目） k的天数； 状态变量：sk是仍待分配的天数（即前面阶段未分配完的天数）
令
P（ixBiblioteka ）表示分配ix 天给考试科目
i 的效果量，我们的目标
是挑选
x
，
1
x
，
2
x
，
3
x
，使
4
max [ P1 ( x1 ) P2 ( x 2 ) P3 ( x 3 ) P4 ( x 4 )]
s.t x 1 x 2 x 3 x 4 7
x
，
1
x
，
2
x
，
3
x
4

1且为整数
目标可改写成
8 4
• 当k=3时;
f3(s3) = max [p3(x3)+ f4(s4) ]
1< x3 < s3 2< sk< 5 计算结果:
S3 X3 p3(x3) F3+ p3 f3(s3) X3*
23 1 12 5 56 7 98 79 11
4 123 568 12 10 10 12 1
5 1 2 34 5 6 88 13 13 12 10 13 1或2
动态规划——资源分配问题

int main() { int i, j,k; int n = 3; int m = 4; //输入数据 cout<<"请输入 3 行 4 列"<<":"<<endl; for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) scanf("%d",&p[i][j]); //打印数据 cout<<"利润表：（行为项目列为资源）"<<endl; cout<<" "; for (j = 1; j <= m; ++j) cout<<setw(4)<<j;//打印框架 m 列 cout<<endl; for (i = 1; i <= n; ++i) { cout<setw(4)<<i;//打印框架 n 行 for (j = 1; j <= m; ++j) cout<<setw(4)<<p[i][j];//打印输入的数据
cout<<endl; }
//主要代码 for (j = 1; j <= m; j++) for (i = 1; i <= n; i++) for (k = 0; k <= i; k++) if (d[i][j] < d[k][j - 1] + p[i - k][j]) { d[i][j] = d[k][j - 1] + p[i - k][j]; e[i][j] = k; }

用动态规划法求解资源分配问题1.某市电信局有四套通讯设备，准备分给甲、乙、丙三个地区支局，事先调查了各地区支局的经营情况，并对各种分配方案作了经济效益的估计，如表所示，其中设备数为0时的收益，指已有的经营收益，问如何分配这四套设备，使总的收益最大？解：分三个阶段1,2,3k =分别对应给甲、乙、丙三个地区支局分配设备，0,1,2,3,4k s =表示在第k 阶段分配的设备套数，()k k x s 表示第k 阶段分配k s 套设备所产生的收益()k k f s 表示将k s 套设备分配给第k 阶段直到第3阶段所产生的收益用逆推法得到基本递推方程1144()max{()()},1,2,3()0k k k k k k f s x s f s k f s ++=+=⎧⎨=⎩ 当3k =时33333(0)48,(1)64,(2)68,(3)78,(4)78f f f f f ===== 当2k =时223(0)max{(0)(00)}max{4840}88f x f =+-=+=23223(0)(1)6440(1)max max 104(1)(0)4248x f f x f ++⎧⎫⎧⎫===⎨⎬⎨⎬++⎩⎭⎩⎭2322323(0)(2)6840(2)max (1)(1)max 64421085048(2)(0)x f f x f x f ++⎧⎫⎧⎫⎪⎪⎪⎪=+=+=⎨⎬⎨⎬⎪⎪⎪⎪++⎩⎭⎩⎭232322323(0)(3)4078(1)(2)6842(3)max max 118(2)(1)64506048(3)(0)x f x f f x f x f ++⎧⎫⎧⎫⎪⎪⎪⎪++⎪⎪⎪⎪===⎨⎬⎨⎬++⎪⎪⎪⎪⎪⎪⎪⎪++⎩⎭⎩⎭23232232323(0)(4)4078(1)(3)4278(4)max (2)(2)max 68501246064(3)(1)6648(4)(0)x f x f f x f x f x f ++⎧⎫⎧⎫⎪⎪⎪⎪++⎪⎪⎪⎪⎪⎪⎪⎪=+=+=⎨⎬⎨⎬⎪⎪⎪⎪++⎪⎪⎪⎪+⎪⎪⎪⎪+⎩⎭⎩⎭当1k =时112(0)max{(0)(0)}max{3888}126f x f =+=+= 12112(1)(0)4188(1)max max 140(0)(1)38102x f f x f ++⎧⎫⎧⎫===⎨⎬⎨⎬++⎩⎭⎩⎭1211212(2)(0)4888(2)max (1)(1)max 4110414638108(0)(2)x f f x f x f ++⎧⎫⎧⎫⎪⎪⎪⎪=+=+=⎨⎬⎨⎬⎪⎪⎪⎪++⎩⎭⎩⎭121211212(3)(0)6088(2)(1)48104(3)max max 156(1)(2)4110838118(0)(3)x f x f f x f x f ++⎧⎫⎧⎫⎪⎪⎪⎪++⎪⎪⎪⎪===⎨⎬⎨⎬++⎪⎪⎪⎪⎪⎪⎪⎪++⎩⎭⎩⎭12121121212(4)(0)6688(3)(1)60104(4)max (2)(2)max 4810816441118(1)(3)38124(0)(4)x f x f f x f x f x f ++⎧⎫⎧⎫⎪⎪⎪⎪++⎪⎪⎪⎪⎪⎪⎪⎪=+=+=⎨⎬⎨⎬⎪⎪⎪⎪++⎪⎪⎪⎪+⎪+⎪⎪⎪⎩⎭⎩⎭故最大收益为164，具体分配方案为甲3套，乙0套，丙1套。