动态规划——资源分配问题 小组成员：黄秀梅 罗燕雯 杨俊 李彩霞 林琳 （女） 吴晶莹 邓桂兰 罗碧辉.

Presentation on theme: "动态规划——资源分配问题 小组成员：黄秀梅 罗燕雯 杨俊 李彩霞 林琳 （女） 吴晶莹 邓桂兰 罗碧辉."— Presentation transcript:

1 动态规划——资源分配问题 小组成员：黄秀梅 罗燕雯 杨俊 李彩霞 林琳 （女） 吴晶莹 邓桂兰 罗碧辉

2 资源分配问题：只有一种资源有待于分配到若干个活动，其目标是如何最有效地在各个活动中分配这种资源。在建立任何效益分配问题的DP(Dynamic Programming )模型时，阶段对应于活动，每个阶段的决策对应于分配到该活动的资源数量；任何状态的当前状态总是等于留待当前阶段和以后阶段分配的资源数量，即总资源量减去前面各阶段已分配的资源量。

3 题目：一名大学生还有7天就要进入有四门考试科目的期末考试。
他想尽可能有效地分配这7天复习时间，每门学科至少需要 1天复习时间。他喜欢每天只复习一门课，所以他可能分配 给每门功课的时间是1，2，3或4天，由于最近学习了运筹学 他希望用DP方法安排时间以使能从这四门课中得到最高的总学 分，他估计每门课的时间分配可能产生的学分如下表。用DP 方法求解这个问题。

4 课程 学分 复习天数 1 2 3 4

5

6

7 当k=4时; f4(s4) = max [p4(x4)] 1< sk< 4 s4 1 2 3 4 x4 1 2 1 2 3
1< xk < sk 1< sk< 4 s4 1 2 3 4 x4 1 2 p4(x4) 2 4 f4(s4) 7 8 X4*

8 当k=3时; f3(s3) = max [p3(x3)+ f4(s4) ] 2< sk< 5 计算结果: S3 2 3 4 5
1< x3 < s3 2< sk< 5 计算结果: S3 2 3 4 5 X3 1 1 2 p3(x3) 5 6 F3+ p3 7 9 8 f3(s3) 9 12 13 X3* 1或2

9 当k=1时; f1(s1) = max [p1(x1)+ f2(s2) ] s1=7 计算结果: S1 7 X1 1 2 3 4
1< x1< s1 s1=7 计算结果: S1 7 X1 P1(x1) F2+ p1 f1(s1) 21 X1* 1

10 当k=2时; f2(s2) = max [p2(x2)+ f3(s3) ] 3< s2< 6 计算结果: S2 3 4 5 6
1< x2 < s2 3< s2< 6 计算结果: S2 3 4 5 6 X2 1 1 2 p2(x2) 3 5 F3+ p2 10 12 12 f2(s2) 12 15 17 X2* 1或2

11