動(dòng)態(tài)規(guī)劃資源分配問(wèn)題

1、動(dòng)態(tài)規(guī)劃資源分配問(wèn)題 1精選ppt資源分配問(wèn)題：只有一種資源有待于分配到若干個(gè)活動(dòng)，其目標(biāo)是如何最有效地在各個(gè)活動(dòng)中分配這種資源。在建立任何效益分配問(wèn)題的DP(Dynamic Programming )模型時(shí)，階段對(duì)應(yīng)于活動(dòng)，每個(gè)階段的決策對(duì)應(yīng)于分配到該活動(dòng)的資源數(shù)量；任何狀態(tài)的當(dāng)前狀態(tài)總是等于留待當(dāng)前階段和以后階段分配的資源數(shù)量，即總資源量減去前面各階段已分配的資源量。2精選ppt 題目：一名大學(xué)生還有7天就要進(jìn)入有四門(mén)考試科目的期末考試。他想盡可能有效地分配這7天復(fù)習(xí)時(shí)間，每門(mén)學(xué)科至少需要1天復(fù)習(xí)時(shí)間。他喜歡每天只復(fù)習(xí)一門(mén)課，所以他可能分配給每門(mén)功課的時(shí)間是1，2，3或4天，由于最近學(xué)習(xí)了

2、運(yùn)籌學(xué)他希望用DP方法安排時(shí)間以使能從這四門(mén)課中得到最高的總學(xué)分，他估計(jì)每門(mén)課的時(shí)間分配可能產(chǎn)生的學(xué)分如下表。用DP方法求解這個(gè)問(wèn)題。3精選ppt 課程 學(xué)分復(fù)習(xí)天數(shù)1 2 3 4 1 2 3 4 3 5 24 5 6 45 6 8 78 7 8 84精選ppt5精選ppt6精選ppt當(dāng)k=4時(shí);f4(s4) = max p4(x4) 1 xk sk 1 sk 4s41 2 3 4x411 21 2 31 2 3 4p4(x4)22 42 4 72 4 7 8f4(s4)2 4 7 8X4*1 2 3 47精選ppt當(dāng)k=3時(shí);f3(s3) = max p3(x3)+ f4(s4) 1 x3

3、s3 2 sk 5計(jì)算結(jié)果:S32 3 4 5X311 21 2 31 2 3 4p3(x3)55 65 6 85 6 8 8F3+ p379 812 10 1013 13 12 10f3(s3)791213X3*1111或28精選ppt當(dāng)k=1時(shí);f1(s1) = max p1(x1)+ f2(s2) 1 x1 s1 s1=7計(jì)算結(jié)果:S1 7X1 1 2 3 4P1(x1) 4 4 5 8F2+ p121 19 17 18f1(s1)21X1*19精選ppt當(dāng)k=2時(shí);f2(s2) = max p2(x2)+ f3(s3) 1 x2 s2 3 s2 6計(jì)算結(jié)果:S23456X211 21 2 31 2 3 4p2(x2)33 53 5 6 3 5 6 7F3+ p21012 1215 14 1316 17 15 14f2(s2)10121517X2*11