文档介绍：动态规划
摆花
【问题描述】(noip2012-3)
小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共 m 盆。通过调查顾客的喜好,小明列出了顾客最喜欢的 n 种花,从1到n标号。为了在门口展出更多种花,规定第 i 种花不能超过 ai 盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算,一共有多少种不同的摆花方案。
【输入】
第一行包含两个正整数 n 和 m,中间用一个空格隔开。
第二行有 n 个整数,每两个整数之间用一个空格隔开,依次表示 a1、a2、……an。
【输出】
输出只有一行,一个整数,表示有多少种方案。注意:因为方案数可能很多,请输出方案数对 1000007 取模的结果。
分析
设f[i,j]表示前i种花放在前j个花盆里的最大方案数,那么 f[i,j]=sum(f[i-1,j-x]) (0<=x<=min(a[i],j)); 解释一下状态转移方程。前J个花盆里,第I种花最少放0个,最多放min(a[i],j)个 边界:f[i,0]=1 (i>=0), f[0,j]:=0 (j>0);
主要参考代码
for i:=1 to n do
for j:=1 to m do
begin
if j<a[i] then l:=j else l:=a[i];
for k:=0 to l do
f[i,j]:=(f[i,j]+f[i-1,j-k])mod 1000007;
end;
阶段
状态
策略
状态转移
带权有向的多段图问题
给定一个带权的有向图,要求从点A到点D的最短路径。
设F(i)表示从点A到达点i的最短距离,则有
F(A)=0
F(B1)=5,F(B2)=2
F(C1)=min{F(B1)+3}=8
F(C2)=min{F(B1)+2,F(B2)+7}=7
F(C3)=min{F(B2)+4}=6
F(D)=min{F(C1)+4,F(C2)+3,F(C3)+5}=10
多阶段最优化决策问题
由上例可以看出,整个问题分成了A、B、C、D四个阶段来做,每个阶段的数值的计算只会跟上一个阶段的数值相关,这样一直递推下去直到目标。
即由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条最优的活动路线。
状态转移方程
设fk(i)—k阶段状态i的最优权值,即初始状态至状态i的最优代价。
fk+1(i) = min{ fk(j) + u(i,j) }
第k+1阶
段状态
第k阶
段状态
决策
算法设计
穷举所有的阶段i
穷举当前阶段i所有可能的状态j
穷举j状态所有对应的子状态的所有可选择的策略k