200分求动态规划详解！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

嗯···我学动归不是很久，同样是迷惘过，估计两个月前刚刚开窍……

你看他写的什么无后效性什么最优子结构的就头大，我也头大%…………

动态规划一般解决两类问题，一类是最优化问题,就是问你最大价值最小数什么的，另一类是方案总数问题。

细分的话类型很多，

我见得多的（我是高二学生，目前在筹备NOIP）

（你那题多我就只说名字了）

背包，楼上连9讲都放上来了我就不多说了……

最长不上升不下降子序列问题（比如说潘帕斯雄鹰生日模拟赛的飞翔，就是很经典的不下降的变形）

资源分配问题（比如说橱窗布置，马棚问题，机器分配问题）

区间动归（乘积最大，能量项链等等）

最长公共子序列问题（有个遗传编码好像）；

解决方案树的比如说爬楼梯问题……………………

动态规划的类型很多很多，因为他很灵活的，我们老师曾经给我们找了100个DP方程，但是那都没有用，强记根本记不住，关键是理解。

深入一点的就有DP的优化，时间空间的降维（就是用别的方法去做，或者比如说背包本来是二维的空间优化过该成一维的了），树形DP（这个我也不会）。

（优化里面有个很经典的题《过河》）

我对DP是属于那种突然就开了窍的……别看说“动态规划”什么的唬人，其实就是一个比较一个计算，知道他干什么了题上来就有头绪，方程啊思想啊就有了……

主要也是多看题吧，从简单的开始，理解他的思想……自己写动归的时候注意下面几个问题：

1、大前提是确定你做的是动归题……看得多了也就知道自己面对的是什么类型的题了

2、次前提是想法要对（我做题的时候先想这道题时间空间的维度，然后根据这个去想方程），方程正确，

实在想不起来可以先看题解，去理解人家的思想之后，不要看标程把程序做出来……

3、注意数组不要开的过小，一般都是左右都开大一点，比如他的数据范围是1~100 ，数组就开0~101这个是防越界的，因为很多DP赋初值的时候会用到F[0],F[0,0]

4、初始值要正确，因为很多DP其他地方都是正确的因为初始值赋错了而全部过不了的情况是很常见的……（比如说USACO里面的货币系统）

5、DP循环的范围要正确，一般根据题来判断范围写多少的（比如说橱窗问题，今天下午写这个题因为循环写错了一直AC不了）

USACO里也有很多DP题，可以做……

以上全部手打，希望能对你有所帮助。

我也是正在学习的人，上面的东西不一定全部正确，但是对我而言很受用，也算是我的经验了。希望日后能一起学习交流外加进步喽

QQ：340131980

1 资源问题1

-----机器分配问题

F[I,j]:=max(f[i-1,k]+w[i,j-k])

2 资源问题2

------01背包问题

F[I,j]:=max(f[i-1,j-v]+w,f[i-1,j]);

3 线性动态规划1

-----朴素最长非降子序列

F:=max{f[j]+1}

4 剖分问题1

-----石子合并

F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);

5 剖分问题2

-----多边形剖分

F[I,j]:=min(f[i,k]+f[k,j]+a[k]a[j]a);

6 剖分问题3

------乘积最大

f[i,j]:=max(f[k,j-1]mult[k,i]);

7 资源问题3

-----系统可靠性(完全背包)

F[i,j]:=max{f[i-1,j-ck]P[I,x]}

8 贪心的动态规划1

-----快餐问题

F[i,j,k]:=max{f[i-1,j',k']+(T-(j-j')p1-(k-k')p2) div p3}

9 贪心的动态规划2

-----过河 f=min{{f(i-k)} (not stone)

{f(i-k)}+1} (stone); +贪心压缩状态

10 剖分问题4

-----多边形-讨论的动态规划

F[i,j]:=max{正正 f[I,k]f[k+1,j];

负负 g[I,k]f[k+1,j];

正负 g[I,k]f[k+1,j];

负正 f[I,k]g[k+1,j];} g为min

11 树型动态规划1

-----加分二叉树 (从两侧到根结点模型)

F[I,j]:=max{f[I,k-1]f[k+1,j]+c[k]}

12 树型动态规划2

-----选课 (多叉树转二叉树,自顶向下模型)

F[I,j]表示以i为根节点选j门功课得到的最大学分

f[i,j]:=max{f[tl,k]+f[tr,j-k-1]+c}

13 计数问题1

-----砝码称重

f[f[0]+1]=f[j]+kw[j];

(1<=i<=n; 1<=j<=f[0]; 1<=k<=a;)

14 递推天地1

------核电站问题

f[-1]:=1; f[0]:=1;

f:=2f[i-1]-f[i-1-m]

15 递推天地2

------数的划分

f[i,j]:=f[i-j,j]+f[i-1,j-1];

16 最大子矩阵1

-----一最大01子矩阵

f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1;

ans:=maxvalue(f);

17 判定性问题1

-----能否被4整除

g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false;

g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j)

18 判定性问题2

-----能否被k整除

f[I,j±n mod k]:=f[i-1,j]; -k<=j<=k; 1<=i<=n

20 线型动态规划2

-----方块消除游戏

f[i,i-1,0]:=0

f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k),

f[i,p,k+len[j]]+f[p+1,j-1,0]}

ans:=f[1,m,0]

21 线型动态规划3

-----最长公共子串，LCS问题

f[i,j]={0(i=0)&(j=0);

f[i-1,j-1]+1 (i>0,j>0,x=y[j]);

max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x<>y[j]);

22 最大子矩阵2

-----最大带权01子矩阵O(n^2m)

枚举行的起始，压缩进数列，求最大字段和，遇0则清零

23 资源问题4

-----装箱问题(判定性01背包)

f[j]:=(f[j] or f[j-v]);

24 数字三角形1

-----朴素の数字三角形

f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);

25 数字三角形2

-----晴天小猪历险记之Hill

同一阶段上暴力动态规划

if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j]

26 双向动态规划1

数字三角形3

-----小胖办证

f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])

27 数字三角形4

-----过河卒

//边界初始化

f[i,j]:=f[i-1,j]+f[i,j-1];

28 数字三角形5

-----朴素的打砖块

f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]);

29 数字三角形6

-----优化的打砖块

f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]}

30 线性动态规划3

-----打鼹鼠’

f:=f[j]+1;(abs(x-x[j])+abs(y-y[j])<=t-t[j])

31 树形动态规划3

-----贪吃的九头龙

32 状态压缩动态规划1

-----炮兵阵地

Max(f[Q(r+1)+k],g[j]+num[k])

If (map and plan[k]=0) and

((plan[P] or plan[q]) and plan[k]=0)

33 递推天地3

-----情书抄写员

f:=f[i-1]+kf[i-2]

34 递推天地4

-----错位排列

f:=(i-1)(f[i-2]+f[i-1]);

f[n]:=nf[n-1]+(-1)^(n-2);

35 递推天地5

-----直线分平面最大区域数

f[n]:=f[n-1]+n

:=n(n+1) div 2 + 1;

36 递推天地6

-----折线分平面最大区域数

f[n]:=(n-1)(2n-1)+2n;

37 递推天地7

-----封闭曲线分平面最大区域数

f[n]:=f[n-1]+2(n-1)

:=sqr(n)-n+2;

38 递推天地8

-----凸多边形分三角形方法数

f[n]:=C(2n-2,n-1) div n;

对于k边形

f[k]:=C(2k-4,k-2) div (k-1); //(k>=3)

39 递推天地9

-----Catalan数列一般形式

1,1,2,5,14,42,132

f[n]:=C(2k,k) div (k+1);

40 递推天地10

-----彩灯布置

排列组合中的环形染色问题

f[n]:=f[n-1](m-2)+f[n-2](m-1); (f[1]:=m; f[2]:=m(m-1);

41 线性动态规划4

-----找数

线性扫描

sum:=f+g[j];

(if sum=Aim then getout; if sum<Aim then inc(i) else inc(j);)

42 线性动态规划5

-----隐形的翅膀

min:=min{abs(w/w[j]-gold)};

if w/w[j]<gold then inc(i) else inc(j);

43 剖分问题5

-----最大奖励

f:=max(f,f[j]+(sum[j]-sum)i-t

44 最短路1

-----Floyd

f[i,j]:=max(f[i,j],f[i,k]+f[k,j]);

ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]s[q[i,j,k],j]/s[i,j];

45 剖分问题6

-----小H的小屋

F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k);

46 计数问题2

-----陨石的秘密（排列组合中的计数问题）

Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D];

F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]f[l1-o,l2-p,l3-q,d]);

47 线性动态规划

------合唱队形

两次F:=max{f[j]+1}＋枚举中央结点

48 资源问题

------明明的预算方案：加花的动态规划

f[i,j]:=max(f[i,j],f[l,j-v-v[fb]-v[fa]]+vp+v[fb]p[fb]+v[fa]p[fa]);

49 资源问题

-----化工场装箱员

50 树形动态规划

-----聚会的快乐

f[i,2]:=max(f[i,0],f[i,1]);

f[i,1]:=sigma(f[t^son,0]);

f[i,0]:=sigma(f[t^son,3]);

51 树形动态规划

-----皇宫看守

f[i,2]:=max(f[i,0],f[i,1]);

f[i,1]:=sigma(f[t^son,0]);

f[i,0]:=sigma(f[t^son,3]);

52 递推天地

-----盒子与球

f[i,1]:=1;

f[i,j]:=j(f[i-1,j-1]+f[i-1,j]);

53 双重动态规划

-----有限的基因序列

f:=min{f[j]+1}

g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or (g[c,i,j])

54 最大子矩阵问题

-----居住空间

f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]),

min(f[i,j,k-1],f[i-1,j-1,k])),

min(min(f[i-1,j,k-1],f[i,j-1,k-1]),

f[i-1,j-1,k-1]))+1;

55 线性动态规划

------日程安排

f:=max{f[j]}+P[I]; (e[j]<s)

56 递推天地

------组合数

C[I,j]:=C[i-1,j]+C[I-1,j-1]

C[I,0]:=1

57 树形动态规划

-----有向树k中值问题

F[I,r,k]:=max{max{f[l,I,j]+f[r,I,k-j-1]},f[f[l,r,j]+f[r,r,k-j]+w[I,r]]}

58 树形动态规划

-----CTSC 2001选课

F[I,j]:=w(if i∈P)+f[l,k]+f[r,m-k](0≤k≤m)(if l<>0)

59 线性动态规划

-----多重历史

f[i,j]:=sigma{f[i-k,j-1]}(if checked)

60 背包问题(+-1背包问题+回溯)

-----CEOI1998 Substract

f[i,j]:=f[i-1,j-a] or f[i-1,j+a]

61 线性动态规划(字符串)

-----NOI 2000 古城之谜

f[i,1,1]:=min{f[i+length(s),2,1], f[i+length(s),1,1]+1}f[i,1,2]:=min{f[i+length(s),1,2]+words[s],f[i+length(s),1,2]+words[s]}

62 线性动态规划

-----最少单词个数

f[i,j]:=max{f[I,j],f[u-1,j-1]+l}

63 线型动态规划

-----APIO2007 数据备份

状态压缩＋剪掉每个阶段j前j2个状态和j2+200后的状态贪心动态规划

f:=min(g[i-2]+s,f[i-1]);

64 树形动态规划

-----APIO2007 风铃

f:=f[l]+f[r]+{1 (if c[l]<c[r])}

g:=1(d[l]<>d[r]) 0(d[l]=d[r])

g[l]=g[r]=1 then Halt;

65 地图动态规划

-----NOI 2005 adv19910

F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j];

66 地图动态规划

-----优化的NOI 2005 adv19910

F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;

67 目标动态规划

-----CEOI98 subtra

F[I,j]:=f[I-1,j+a] or f[i-1,j-a]

68 目标动态规划

----- Vijos 1037搭建双塔问题

F[value,delta]:=g[value+a,delta+a] or g[value,delta-a]

69 树形动态规划

-----有线电视网

f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j])

leaves>=p>=l, 1<=q<=p;

70 地图动态规划

-----vijos某题

F[I,j]:=min(f[i-1,j-1],f[I,j-1],f[i-1,j]);

71 最大子矩阵问题

-----最大字段和问题

f:=max(f[i-1]+b,b); f[1]:=b[1]

72 最大子矩阵问题

-----最大子立方体问题

枚举一组边i的起始，压缩进矩阵 B[I,j]+=a[x,I,j]

枚举另外一组边的其实，做最大子矩阵

73 括号序列

-----线型动态规划

f[I,j]:=min(f[I,j],f[i+1,j-1](ss[j]=”()”or(”[]”)),

f[I+1,j+1]+1 (s[j]=”(”or”[” ] , f[I,j-1]+1(s[j]=”)”or”]” )

74 棋盘切割

-----线型动态规划

f[k,x1,y1,x2,y2]=min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2],

f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]

min{}}

75 概率动态规划

-----聪聪和可可(NOI2005)

x:=p[p[i,j],j]

f[I,j]:=(f[x,b[j,k]]+f[x,j])/(l[j]+1)+1

f[I,i]=0

f[x,j]=1

76 概率动态规划

-----血缘关系

F[A, B]=(f[A0, B]+P[A1, B])/2

f[I,i]=1

f[I,j]=0(I,j无相同基因)

77 线性动态规划

-----决斗

F[I,j]=(f[I,j] and f[k,j]) and (e[I,k] or e[j,k]),i<k<j

78 线性动态规划

-----舞蹈家

F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w[y,a[k]])

79 线性动态规划

-----积木游戏

F[I,a,b,k]=max(f[I,a+1,b,k],f[i+1,a+1,a+1,k’],f[I,a+1,a+1,k’])

80 树形动态规划（双次记录）

-----NOI2003 逃学的小孩

朴素的话枚举节点i和离其最远的两个节点 j,k O(n^2)

每个节点记录最大的两个值，并记录这最大值分别是从哪个相邻节点传过来的。当遍历到某个孩子节点的时候，只需检查最大值是否是从该孩子节点传递来的。如果是，就取次大，否则取最大值

81 树形动态规划(完全二叉树)

-----NOI2006 网络收费

F[I,j,k]表示在点i所管辖的所有用户中，有j个用户为A，在I的每个祖先u上，如果N[a]>N则标0否则标1，用二进制状态压缩进k中，在这种情况下的最小花费

F[I,j,k]:=min{f[l,u,k and (s<<(i-1))]+w1,f[r,j-u,k and(s<<(i-1))]}

82 树形动态规划

-----IOI2005 河流

F:=max

83 记忆化搜索

-----Vijos某题,忘了

F[pre,h,m]:=sigma{SDP(I,h+1,M+i)} (pre<=i<=M＋1)

84 状态压缩动态规划

-----APIO 2007 动物园

f[I,k]:=f[i-1,k and not (1<<4)] + NewAddVal

85 树形动态规划

-----访问术馆

f[i,j-c×2]:= max ( f[l,k], f[r,j-c×2-k] )

86 字符串动态规划

-----Ural 1002 Phone

if exist(copy(s,j,i-j)) then f:=min(f,f[j]+1);

87 多进程动态规划

-----CEOI 2005 service

Min( f[i,j,k], f[i-1,j,k] + c[t[i-1],t] )

Min( f[i,t[i-1],k], f[i-1,j,k] + c[j,t] )

Min( f[i,j,t[i-1]], f[i-1,j,k] + c[k,t] )

88 多进程动态规划

-----Vijos1143 三取方格数

max(f[i,j,k,l],f[i-1,j-R[m,1],k-R[m,2],l-R[m,3]]);

if (j=k) and (k=l) then inc(f[i,j,k,l],a[j,i-j]) else

if (j=k) then inc(f[i,j,k,l],a[j,i-j]+a[l,i-l]) else

if (k=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else

if (j=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else

inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]+a[l,i-l]);

89 线型动态规划

-----IOI 2000 邮局问题

f[i,j]:=min(f[I,j],f[k,j-1]+d[k+1,i]);

90 线型动态规划

-----Vijos 1198 最佳课题选择

if j-k>=0 then Min(f[i,j],f[i-1,j-k]+time(i,k));

91 背包问题

----- USACO Raucous Rockers

多个背包，不可以重复放物品，但放物品的顺序有限制。

F[I,j,k]表示决策到第i个物品、第j个背包，此背包花费了k的空间。

f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t])

92 多进程动态规划

-----巡游加拿大（IOI95、USACO）

d[i,j]=max{d[k,j]+1(a[k,i] & j<k<i),d[j,k]+1(a[I,j] & (k<j))}。

f[i,j]表示从起点出发，一个人到达i，另一个人到达j时经过的城市数。d[i,j]=d[j,i]，所以我们限制i>j

分析状态(i,j)，它可能是(k,j)(j<k<i)中k到达i得到（方式1），也可能是(j,k)(k<j)中k超过j到达i得到（方式2）。但它不能是(i,k)(k<j)中k到达j得到，因为这样可能会出现重复路径。即使不会出现重复路径，那么它由(j,k)通过方式2同样可以得到，所以不会遗漏解 时间复杂度O(n3)

93 动态规划

-----ZOJ cheese

f[i,j]:=f[i-kkzl[u,1],j-kkzl[u,2]]+a[i-kkzl[u,1],j-kkzl[u,2]]

94 动态规划

-----NOI 2004 berry 线性

F[I,1]:=s

F[I,j]:=max{min{s-s[l-1]},f[l-1,j-1]} (2≤j≤k, j≤l≤i)

95 动态规划

-----NOI 2004 berry 完全无向图

F[I,j]:=f[i-1,j] or (j≥w) and (f[i-1,j-w])

96 动态规划

-----石子合并 四边形不等式优化

m[i,j]=max{m[i+1,j], m[i,j-1]}+t[i,j]

97 动态规划

-----CEOI 2005 service

（k≥long，i≥1）g[i, j, k]=max{g[i-1,j,k-long]+1，g[i-1,j,k]}

（k<long，i≥1） g[i, j, k]=max{g[i-1,j-1,t-long]+1，g[i-1,j,k]}

(0≤j≤m， 0≤k<t) g[0,j,k]=0;

ans:=g[n,m,0]。

状态优化：g[i, j]=min{g[i-1,j]，g[i-1,j-1]+long}

其中(a, b)+long=(a’, b’)的计算方法为：

当b+long ≤t时： a’=a; b’=b+long;

当b+long ＞t时： a’=a+1; b’=long;

规划的边界条件：

当0≤i≤n时，g[i,0]=(0,0)

98 动态规划

-----AHOI 2006宝库通道

f[k]:=max{f[k-1]+x[k,j]-x[k,i-1], x[k,j]-x[k,i-1]}

99 动态规划

-----Travel

A) 费用最少的旅行计划。

设f表示从起点到第i个旅店住宿一天的最小费用；g表示从起点到第i个旅店住宿一天，在满足最小费用的前提下所需要的最少天数。那么：

f=f[x]+v, g=g[x]+1

x满足：

1、 x<i，且d – d[x] <= 800（一天的最大行程）。

2、 对于所有的t < i, d – d[t] <= 800，都必须满足：

A g[x] < g[t](f[x] = f[t]时) B f[x] < f[t] (其他情况)

f[0] = 0，g[0] = 0。 Ans:=f[n + 1]，g[n+1]。

B) 天数最少的旅行计划。

方法其实和第一问十分类似。

设g’表示从起点到第i个旅店住宿一天的最少天数；f’表示从起点到第i个旅店住宿一天，在满足最小天数前提下所需要的最少费用。那么：

g’ = g’[x] + 1, f’ = f’[x] + v

x满足：

1、 x<i，且d – d[x] <= 800（一天的最大行程）。

2、 对于所有的t < i, d – d[t] <= 800，都必须满足：

f’[x] < f’[t] g’[x] = g’[t]时

g’[x] < g’[t] 其他情况

f’[0] = 0，g’[0] = 0。 Ans:=f’[n + 1]，g’[n+1]。

100 动态规划

-----NOI 2007 cash

y:=f[j]/(a[j]c[j]+b[j]);

g:=c[j]ya+yb;

f:=max(f,g)

一个旅行者有一个最多能用M公斤的背包，现在有N件物品，

它们的重量分别是W1，W2，,Wn,

它们的价值分别为P1,P2,,Pn

若每种物品只有一件求旅行者能获得最大总价值。

输入格式：

M,N

W1,P1

W2,P2

输出格式：

X

/

因为背包最大容量M未知。所以，我们的程序要从1到M一个一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。

测试数据：

10,3

3,4

4,5

5,6

c[i][j]数组保存了1,2,3号物品依次选择后的最大价值

这个最大价值是怎么得来的呢从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放所以置0,背包容量为3则里面放4这样,这一排背包容量为4,5,6,10的时候，最佳方案都是放4假如1号物品放入背包则再看2号物品当背包容量为3的时候，最佳方案还是上一排的最价方案c为4而背包容量为5的时候，则最佳方案为自己的重量5背包容量为7的时候，很显然是5加上一个值了。加谁很显然是7-4=3的时候上一排 c3的最佳方案是4所以。总的最佳方案是5+4为9这样一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6而是上一排的9说明这时候3号物品没有被选选的是1,2号物品所以得9)

从以上最大价值的构造过程中可以看出。

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程这回清楚了吗

下面是实际程序:

#include<stdioh>

int c[10][100];/对应每种情况的最大价值/

int knapsack(int m,int n)

{

int i,j,w[10],p[10];

for(i=1;i<n+1;i++)

scanf("\n%d,%d",&w[i],&p[i]);

for(i=0;i<10;i++)

for(j=0;j<100;j++)

c[i][j]=0;/初始化数组/

for(i=1;i<n+1;i++)

for(j=1;j<m+1;j++)

{

if(w[i]<=j) /如果当前物品的容量小于背包容量/

{

if(p[i]+c[i-1][j-w[i]]>c[i-1][j])

/如果本物品的价值加上背包剩下的空间能放的物品的价值/

/大于上一次选择的最佳方案则更新c[i][j]/

c[i][j]=p[i]+c[i-1][j-w[i]];

else

c[i][j]=c[i-1][j];

}

else c[i][j]=c[i-1][j];

}

return(c[n][m]);

}

int main()

{

int m,n;int i,j;

scanf("%d,%d",&m,&n);

printf("Input each one:\n");

printf("%d",knapsack(m,n));

printf("\n");/下面是测试这个数组,可删除/

for(i=0;i<10;i++)

for(j=0;j<15;j++)

{

printf("%d ",c[i][j]);

if(j==14)printf("\n");

}

system("pause");

}

动态规划算法 概念及意义动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家REBellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 基本模型

多阶段决策过程的最优化问题。

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图）

这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 记忆化搜索 给你一个数字三角形, 形式如下:

1

2 3

4 5 6

7 8 9 10

找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大

无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)}

对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。

解决方法：

我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程 :

f1:=f(i-1,j+1); f2:=f(i-1,j);

if f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j];

显而易见，这个算法就是最简单的搜索算法。时间复杂度为2^n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：Opt[i, j] - 每产生一个f(i, j)，将f(i, j)的值放入opt中，以后再次调用到f(i, j)的时候，直接从opt[i, j]来取就可以了。于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，避免了动态规划状态转移先后的问题，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的 状态 决策

决策：

当前状态通过决策,回到了以前状态可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。

状态：

我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。有时候当前状态确定后,以前状态就已经确定,则无需枚举

动态规划算法的应用 一、动态规划的概念

近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。

要了解动态规划的概念，首先要知道什么是多阶段决策问题。

1 多阶段决策问题

如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。

各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果

2．动态规划问题中的术语

阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。

在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。

状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。

在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。

过程的状态通常可以用一个或一组数来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。

当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。

无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。

决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多间题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。

决策变量的范围称为允许决策集合。

策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。

给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k)，u(k))与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程。

最优性原理:作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。

最优性原理实际上是要求问题的最优策略的子策略也是最优。让我们通过对前面的例子再分析来具体说明这一点：从A到D，我们知道，最短路径是A�8�1B1�8�1C2�8�1D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：A�8�1B1�8�1C2是A到C2的最短路径，B1�8�1C2�8�1D也是B1到D的最短路径……──事实正是如此，因此我们认为这个例子满足最优性原理的要求。

这是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱

动态规划首次进入信息学奥赛是在IOI94（数字三角形），在国内首次出现是在NOI95。此后动态规划成为信息学奥赛的必考算法之一。

[编辑本段]概念及意义

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家REBellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

[编辑本段]基本模型

多阶段决策过程的最优化问题。

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图）

这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。

[编辑本段]记忆化搜索

给你一个数字三角形, 形式如下:

1

2 3

4 5 6

7 8 9 10

找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大

无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)}

对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。

动态规划的特点及其应用

安徽 张辰

目 录

(点击进入)

关键词

摘要

正文

§1动态规划的本质

§11多阶段决策问题

§12阶段与状态

§13决策和策略

§14最优化原理与无后效性

§15最优指标函数和规划方程

§2动态规划的设计与实现

§21动态规划的多样性

§22动态规划的模式性

§23动态规划的技巧性

§3动态规划与一些算法的比较

§31动态规划与递推

§32动态规划与搜索

§33动态规划与网络流

§4结语

附录：部分试题与源程序

1“花店橱窗布置问题”试题

2“钉子与小球”试题

3例2“花店橱窗布置问题”方法1的源程序

4例2“花店橱窗布置问题”方法2的源程序

5例3“街道问题”的扩展

6例4“mod 4最优路径问题”的源程序

7例5“钉子与小球”的源程序

8例6的源程序,“N个人的街道问题”

参考文献

关键词动态规划 阶段

摘要

动态规划是信息学竞赛中的常见算法，本文的主要内容就是分析它的特点。

文章的第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技巧性这三个特点。第三部分将动态规划和递推、搜索、网络流这三个相关算法作了比较，从中探寻动态规划的一些更深层次的特点。

文章在分析动态规划的特点的同时，还根据这些特点分析了我们在解题中应该怎样利用这些特点，怎样运用动态规划。这对我们的解题实践有一定的指导意义。

正文

动态规划是编程解题的一种重要的手段，在如今的信息学竞赛中被应用得越来越普遍。最近几年的信息学竞赛，不分大小，几乎每次都要考察到这方面的内容。因此，如何更深入地了解动态规划，从而更为有效地运用这个解题的有力武器，是一个值得深入研究的问题。

要掌握动态规划的应用技巧，就要了解它的各方面的特点。首要的，是要深入洞悉动态规划的本质。

§1动态规划的本质

动态规划是在本世纪50年代初，为了解决一类多阶段决策问题而诞生的。那么，什么样的问题被称作多阶段决策问题呢？

§11多阶段决策问题

说到多阶段决策问题，人们很容易举出下面这个例子。

[例1] 多段图中的最短路径问题：在下图中找出从A1到D1的最短路径。

仔细观察这个图不难发现，它有一个特点。我们将图中的点分为四类（图中的A、B、C、D），那么图中所有的边都处于相邻的两类点之间，并且都从前一类点指向后一类点。这样，图中的边就被分成了三类（AB、BC、CD）。我们需要从每一类中选出一条边来，组成从A1到D1的一条路径，并且这条路径是所有这样的路径中的最短者。

从上面的这个例子中，我们可以大概地了解到什么是多阶段决策问题。更精确的定义如下：

多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列[1]。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。

从上述的定义中，我们可以明显地看出，这类问题有两个要素。一个是阶段，一个是决策。

§12阶段与状态

阶段：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。常用字母k表示阶段变量。[1]

阶段是问题的属性。多阶段决策问题中通常存在着若干个阶段，如上面的例子，就有A、B、C、D这四个阶段。在一般情况下，阶段是和时间有关的；但是在很多问题（我的感觉，特别是信息学问题）中，阶段和时间是无关的。从阶段的定义中，可以看出阶段的两个特点，一是“相互联系”，二是“次序”。

阶段之间是怎样相互联系的？就是通过状态和状态转移。

状态：各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为状态集合，用Sk表示。[1]

状态是阶段的属性。每个阶段通常包含若干个状态，用以描述问题发展到这个阶段时所处在的一种客观情况。在上面的例子中，行人从出发点A1走过两个阶段之后，可能出现的情况有三种，即处于C1、C2或C3点。那么第三个阶段就有三个状态S3={C1,C2,C3}。

每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移（暂不定义）。上例中C3点可以从B1点过来，也可以从B2点过来，从阶段2的B1或B2状态走到阶段3的C3状态就是状态转移。状态转移是导出状态的途径，也是联系各阶段的途径。

说到这里，可以提出应用动态规划的一个重要条件。那就是将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的发展，而只能通过当前的这个状态。换句话说，每个状态都是“过去历史的一个完整总结[1]”。这就是无后效性。对这个性质，下文还将会有解释。

§13决策和策略

上面的阶段与状态只是多阶段决策问题的一个方面的要素，下面是另一个方面的要素——决策。

决策：当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。显然有uk(sk) Dk(sk)。[1]

决策是问题的解的属性。决策的目的就是“确定下一阶段的状态”，还是回到上例，从阶段2的B1状态出发有三条路，也就是三个决策，分别导向阶段3的C1、C2、C3三个状态，即D2(B1)={C1,C2,C3}。

有了决策，我们可以定义状态转移：动态规划中本阶段的状态往往是上一阶段和上一阶段的决策结果，由第k段的状态sk和本阶段的决策uk确定第k+1段的状态sk+1的过程叫状态转移。状态转移规律的形式化表示sk+1=Tk(sk,uk)称为状态转移方程。

这样看来，似乎决策和状态转移有着某种联系。我的理解，状态转移是决策的目的，决策是状态转移的途径。

各段决策确定后，整个问题的决策序列就构成一个策略，用p1,n={u1(s1),u2(s2),…, un(sn)}表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最有效果的策略就是最优策略。[1]

说到这里，又可以提出运用动态规划的一个前提。即这个过程的最优策略应具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略[1]。这就是最优化原理。简言之，就是“最优策略的子策略也是最优策略”。

§14最优化原理与无后效性

这里，我把最优化原理定位在“运用动态规划的前提”。这是因为，是否符合最优化原理是一个问题的本质特征。对于不满足最优化原理的一个多阶段决策问题，整体上的最优策略p1,n同任何一个阶段k上的决策uk或任何一组阶段k1…k2上的子策略pk1,k2都不存在任何关系。如果要对这样的问题动态规划的话，我们从一开始所作的划分阶段等努力都将是徒劳的。

而我把无后效性定位在“应用动态规划的条件”，是因为动态规划是按次序去求每阶段的解，如果一个问题有后效性，那么这样的次序便是不合理的。但是，我们可以通过重新划分阶段，重新选定状态，或者增加状态变量的个数等手段，来是问题满足无后效性这个条件。说到底，还是要确定一个“序”。

在信息学的多阶段决策问题中，绝大部分都是能够满足最优化原理的，但它们往往会在后效性这一点上来设置障碍。所以在解题过程中，我们会特别关心“序”。对于有序的问题，就会考虑到动态规划；对于无序的问题，也会想方设法来使其有序。

§15最优指标函数和规划方程

最优指标函数：用于衡量所选定策略优劣的数量指标称为指标函数，最优指标函数记为fk(sk)，它表示从第k段状态sk采用最优策略pk,n到过程终止时的最佳效益值[1]。

最优指标函数其实就是我们真正关心的问题的解。在上面的例子中，f2(B1)就表示从B1点到终点D1点的最短路径长度。我们求解的最终目标就是f1(A1)。

最优指标函数的求法一般是一个从目标状态出发的递推公式，称为规划方程：

其中sk是第k段的某个状态，uk是从sk出发的允许决策集合Dk(sk)中的一个决策，Tk(sk,uk)是由sk和uk所导出的第k+1段的某个状态sk+1，g(x,uk)是定义在数值x和决策uk上的一个函数，而函数opt表示最优化，根据具体问题分别表为max或min。

，称为边界条件。

上例中的规划方程就是：

边界条件为

这里是一种从目标状态往回推的逆序求法，适用于目标状态确定的问题。在我们的信息学问题中，也有很多有着确定的初始状态。当然，对于初始状态确定的问题，我们也可以采用从初始状态出发往前推的顺序求法。事实上，这种方法对我们来说要更为直观、更易设计一些，从而更多地出现在我们的解题过程中。

我们本节所讨论的这些理论虽然不是本文的主旨，但是却对下面要说的动态规划的特点起着基础性的作用。

§2动态规划的设计与实现

上面我们讨论了动态规划的一些理论，本节我们将通过几个例子中，动态规划的设计与实现，来了解动态规划的一些特点。

§21动态规划的多样性

[例2] 花店橱窗布置问题（IOI99）试题见附录

本题虽然是本届IOI中较为简单的一题，但其中大有文章可作。说它简单，是因为它有序，因此我们一眼便可看出这题应该用动态规划来解决。但是，如何动态规划呢？如何划分阶段，又如何选择状态呢？

<方法1>以花束的数目来划分阶段。在这里，阶段变量k表示的就是要布置的花束数目（前k束花），状态变量sk表示第k束花所在的花瓶。而对于每一个状态sk，决策就是第k-1束花应该放在哪个花瓶，用uk表示。最优指标函数fk(sk)表示前k束花，其中第k束插在第sk个花瓶中，所能取得的最大美学值。

状态转移方程为

规划方程为

（其中A(i,j)是花束i插在花瓶j中的美学值）

边界条件 （V是花瓶总数，事实上这是一个虚拟的边界）

<方法2>以花瓶的数目来划分阶段。在这里阶段变量k表示的是要占用的花瓶数目（前k个花瓶），状态变量sk表示前k个花瓶中放了多少花。而对于任意一个状态sk，决策就是第sk束花是否放在第k个花瓶中，用变量uk=1或0来表示。最优指标函数fk(sk)表示前k个花瓶中插了sk束花，所能取得的最大美学值。

状态转移方程为

规划方程为

边界条件为

两种划分阶段的方法，引出了两种状态表示法，两种规划方式，但是却都成功地解决了问题。只不过因为决策的选择有多有少，所以算法的时间复杂度也就不同。[2]

这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方法，因而往往就有不止一种的规划方法。有时各种方法所产生的效果是差不多的，但更多的时候，就像我们的例子一样，两种方法会在某个方面有些区别。

所以，在用动态规划解题的时候，可以多想一想是否有其它的解法。对于不同的解法，要注意比较，好的算法好在哪里，差一点的算法差在哪里。从各种不同算法的比较中，我们可以更深刻地领会动态规划的构思技巧。

§22动态规划的模式性

这个可能做过动态规划的人都有体会，从我们上面对动态规划的分析也可以看出来。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的，否则问题就无法求解。

选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。

写出规划方程（包括边界条件）：在第一部分中，我们已经给出了规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。

动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。大体上的框架如下：

对f1(s1)初始化（边界条件）

for k2 to n（这里以顺序求解为例）

对每一个skSk

fk(sk)一个极值（∞或－∞）

对每一个uk(sk)Dk(sk)

sk-1Tk(sk,uk)

tg(fk-1(sk-1),uk)

y t比fk(sk)更优 n

fk(sk)t

输出fn(sn)

这个N-S图虽然不能代表全部，但足可以概括大多数。少数的一些特殊的动态规划，其实现的原理也是类似，可以类比出来。我们到现在对动态规划的分析，主要是在理论上、设计上，原因也就在此。

掌握了动态规划的模式性，我们在用动态规划解题时就可以把主要的精力放在理论上的设计。一旦设计成熟，问题也就基本上解决了。而且在设计算法时也可以按部就班地来。

但是“物极必反”，太过拘泥于模式就会限制我们的思维，扼杀优良算法思想的产生。我们在解题时，不妨发挥一下创造性，去突破动态规划的实现模式，这样往往会收到意想不到的效果。[3]

§23动态规划的技巧性

上面我们所说的动态规划的模式性，主要指的是实现方面。而在设计方面，虽然它较为严格的步骤性，但是它的设计思想却是没有一定的规律可循的。这就需要我们不断地在实践当中去掌握动态规划的技巧，下面仅就一个例子谈一点我自己的体会。

[例3] 街道问题：在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。

这是一道简单而又典型的动态规划题，许多介绍动态规划的书与文章中都拿它来做例子。通常，书上的解答是这样的：

按照图中的虚线来划分阶段，即阶段变量k表示走过的步数，而状态变量sk表示当前处于这一阶段上的哪一点（各点所对应的阶段和状态已经用ks在地图上标明）。这时的模型实际上已经转化成了一个特殊的多段图。用决策变量uk=0表示向右走，uk=1表示向上走，则状态转移方程如下：

（这里的row是地图竖直方向的行数）

我们看到，这个状态转移方程需要根据k的取值分两种情况讨论，显得非常麻烦。相应的，把它代入规划方程而付诸实现时，算法也很繁。因而我们在实现时，一般是不会这么做的，而代之以下面方法：

将地图中的点规则地编号如上，得到的规划方程如下：

（这里Distance表示相邻两点间的边长）

这样做确实要比上面的方法简单多了，但是它已经破坏了动态规划的本来面目，而不存在明确的阶段特征了。如果说这种方法是以地图中的行（A、B、C、D）来划分阶段的话，那么它的“状态转移”就不全是在两个阶段之间进行的了。

也许这没什么大不了的，因为实践比理论更有说服力。但是，如果我们把题目扩展一下：在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要求两条路径的总长度最短。这时，再用这种“简单”的方法就不太好办了。

如果非得套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以处理两条路径“不能重叠”的问题。

而我们回到原先“标准”的动态规划法，就会发现这个问题很好解决，只需要加一维状态变量就成了。即用sk=(ak,bk)分别表示两条路径走到阶段k时所处的位置，相应的，决策变量也增加一维，用uk=(xk,yk)分别表示两条路径的行走方向。状态转移时将两条路径分别考虑：

在写规划方程时，只要对两条路径走到同一个点的情况稍微处理一下，减少可选的决策个数：

从这个例子中可以总结出设计动态规划算法的一个技巧：状态转移一般是在相邻的两个阶段之间（有时也可以在不相邻的两个阶段间），但是尽量不要在同一个阶段内进行。

动态规划是一种很灵活的解题方法，在动态规划算法的设计中，类似的技巧还有很多。要掌握动态规划的技巧，有两条途径：一是要深刻理解动态规划的本质，这也是我们为什么一开始就探讨它的本质的原因；二是要多实践，不但要多解题，还要学会从解题中探寻规律，总结技巧。

§3动态规划与一些算法的比较

动态规划作为诸多解题方法中的一种，必然和其他一些算法有着诸多联系。从这些联系中，我们也可以看出动态规划的一些特点。

§31动态规划与递推

——动态规划是最优化算法

由于动态规划的“名气”如此之大，以至于很多人甚至一些资料书上都往往把一种与动态规划十分相似的算法，当作是动态规划。这种算法就是递推。实际上，这两种算法还是很容易区分的。

按解题的目标来分，信息学试题主要分四类：判定性问题、构造性问题、计数问题和最优化问题。我们在竞赛中碰到的大多是最优化问题，而动态规划正是解决最优化问题的有力武器，因此动态规划在竞赛中的地位日益提高。而递推法在处理判定性问题和计数问题方面也是一把利器。下面分别就两个例子，谈一下递推法和动态规划在这两个方面的联系。

[例4] mod 4 最优路径问题：在下图中找出从第1点到第4点的一条路径，要求路径长度mod 4的余数最小。

这个图是一个多段图，而且是一个特殊的多段图。虽然这个图的形式比一般的多段图要简单，但是这个最优路径问题却不能用动态规划来做。因为一条从第1点到第4点的最优路径，在它走到第2点、第3点时，路径长度mod 4的余数不一定是最小，也就是说最优策略的子策略不一定最优——这个问题不满足最优化原理。

但是我们可以把它转换成判定性问题，用递推法来解决。判断从第1点到第k点的长度mod 4为sk的路径是否存在，用fk(sk)来表示，则递推公式如下：

（边界条件）

（这里lenk,i表示从第k-1点到第k点之间的第i条边的长度，方括号表示“或(or)”运算）

最后的结果就是可以使f4(s4)值为真的最小的s4值。

这个递推法的递推公式和动态规划的规划方程非常相似，我们在这里借用了动态规划的符号也就是为了更清楚地显示这一点。其实它们的思想也是非常相像的，可以说是递推法借用了动态规划的思想解决了动态规划不能解决的问题。

有的多阶段决策问题（像这一题的阶段特征就很明显），由于不能满足最优化原理等使用动态规划的先决条件，而无法应用动态规划。在这时可以将最优指标函数的值当作“状态”放到下标中去，从而变最优化问题为判定性问题，再借用动态规划的思想，用递推法来解决问题。

[例5] 钉子与小球（NOI99）试题见附录

这个题目一看就不觉让人想起一道经典的动态规划题。下面先让我们回顾一下这个问题。

数字三角形（IOI94）在下图中求从顶至低某处的一条路径，使该路径所经过的数字的总和最大，每一步只能向左下或右下走。

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

在这个问题中，我们按走过的行数来划分阶段，以走到每一行时所在的位置来作为状态，决策就是向左下走（用0表示）或向右下走（用1表示）。

状态转移方程：

规划方程：

边界条件：

这是一个比较简单的最优化问题，我们还可以把这个问题改成一个更加简单的整数统计问题：求顶点到每一点的路径总数。把这个总数用fk(sk)表示，那么递推公式就是：

在这里，虽然求和公式只有两项，但我们仍然用∑的形式表示，就是为了突出这个递推公式和上面的规划方程的相似之处。这两个公式的边界条件都是一模一样的。

再回到我们上面的“钉子与小球”问题，这是一个概率统计问题。我们继续沿用上面的思想，用fk(sk)表示小球落到第k行第sk个钉子上的概率，则递推公式如下：

（这里函数Existk(sk)表示第k行第sk个钉子是否存在，存在则取1，不存在则取0）

边界条件

可以看出这个公式较之上面的两个式子虽然略有变化，但是其基本思想还是类似的。在解这个问题的过程中，我们再次运用了动态规划的思想。

一般说来，很多最优化问题都有着对应的计数问题；反过来，很多计数问题也有着对应的最优化问题。因此，我们在遇到这两类问题时，不妨多联系、多发展，举一反三，从比较中更深入地理解动态规划的思想。

其实递推和动态规划这两种方法的思想本来就很相似，也不必说是谁借用了谁的思想。关键在于我们要掌握这种思想，这样我们无论在用动态规划法解最优化问题，或是在用递推法解判定型、计数问题时，都能得心应手、游刃有余了。

§32动态规划与搜索

——动态规划是高效率、高消费算法

同样是解决最优化问题，有的题目我们采用动态规划，而有的题目我们则需要用搜索。这其中有没有什么规则呢？

我们知道，撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索可以说是“万能”的。所以动态规划可以解决的问题，搜索也一定可以解决。

把一个动态规划算法改写成搜索是非常方便的，状态转移方程、规划方程以及边界条件都可以直接“移植”，所不同的只是求解顺序。动态规划是自底向上的递推求解，而搜索则是自顶向下的递归求解（这里指深度搜索，宽度搜索类似）。

反过来，我们也可以把搜索算法改写成动态规划。状态空间搜索实际上是对隐式图中的点进行枚举，这种枚举是自顶向下的。如果把枚举的顺序反过来，变成自底向上，那么就成了动态规划。（当然这里有个条件，即隐式图中的点是可排序的，详见下一节。）

正因为动态规划和搜索有着求解顺序上的不同，这也造成了它们时间效率上的差别。在搜索中，往往会出现下面的情况：

对于上图(a)这样几个状态构成的一个隐式图，用搜索算法就会出现重复，如上图(b)所示，状态C2被搜索了两次。在深度搜索中，这样的重复会引起以C2为根整个的整个子搜索树的重复搜索；在宽度搜索中，虽然这样的重复可以立即被排除，但是其时间代价也是不小的。而动态规划就没有这个问题，如上图(c)所示。

一般说来，动态规划算法在时间效率上的优势是搜索无法比拟的。（当然对于某些题目，根本不会出现状态的重复，这样搜索和动态规划的速度就没有差别了。）而从理论上讲，任何拓扑有序（现实中这个条件常常可以满足）的隐式图中的搜索算法都可以改写成动态规划。但事实上，在很多情况下我们仍然不得不采用搜索算法。那么，动态规划算法在实现上还有什么障碍吗？

考虑上图(a)所示的隐式图，其中存在两个从初始状态无法达到的状态。在搜索算法中，这样的两个状态就不被考虑了，如上图(b)所示。但是动态规划由于是自底向上求解，所以就无法估计到这一点，因而遍历了全部的状态，如上图(c)所示。

一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的事搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。

如何协调好动态规划的高效率与高消费之间的矛盾呢？有一种折衷的办法就是记忆化算法。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。

§33动态规划与网络流

——动态规划是易设计易实现算法

由于图的关系复杂而无序，一般难以呈现阶段特征（除了特殊的图如多段图，或特殊的分段方法如Floyd），因此动态规划在图论中的应用不多。但有一类图，它的点却是有序的，这就是有向无环图。

在有向无环图中，我们可以对点进行拓扑排序，使其体现出有序的特征，从而据此划分阶段。在有向无还图中求最短路径的算法[4]，已经体现出了简单的动态规划思想。但动态规划在图论中还有更有价值的应用。下面先看一个例子。

[例6] N个人的街道问题：在街道问题（参见例3）中，若有N个人要从左下角走向右上角，要求他们走过的边的总长度最大。当然，这里每个人也只能向右或向上走。下面是一个样例，左图是从出发地到目的地的三条路径，右图是他们所走过的边，这些边的总长度为5 + 4 + 3 + 6 + 3 + 3 + 5 + 8 + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78（不一定是最大）。

这个题目是对街道问题的又一次扩展。仿照街道问题的解题方法，我们仍然可以用动态规划来解决本题。不过这一次是N个人同时走，状态变量也就需要用N维来表示，。相应的，决策变量也要变成N维，uk=(uk,1,uk,2,…,uk,N)。状态转移方程不需要做什么改动：

在写规划方程时，需要注意在第k阶段，N条路径所走过的边的总长度的计算，在这里我就用gk(sk,uk)来表示了：

边界条件为

可见将原来的动态规划算法移植到这个问题上来，在理论上还是完全可行的。但是，现在的这个动态规划算法的时空复杂度已经是关于N的指数函数，只要N稍微大一点，这个算法就不可能实现了。

下面我们换一个思路，将N条路径看成是网络中一个流量为N的流，这样求解的目标就是使这个流的费用最大。但是本题又不同于一般的费用流问题，在每一条边e上的流费用并不是流量和边权的乘积 ，而是用下式计算：

为了使经典的费用流算法适用于本题，我们需要将模型稍微转化一下：

如图，将每条边拆成两条。拆开后一条边上有权，但是容量限制为1；另一条边没有容量限制，但是流过这条边就不能计算费用了。这样我们就把问题转化成了一个标准的最大费用固定流问题。

这个算法可以套用经典的最小费用最大流算法，在此就不细说了。（参见附录中的源程序）

这个例题是我仿照IOI97的“障碍物探测器”一题[6]编出来的。“障碍物探

一动态规划求解0-1背包问题

//

/ 0-1背包问题：

/ 给定n种物品和一个背包

/ 物品i的重量为wi，其价值为vi

/ 背包的容量为c

/ 应如何选择装入背包的物品，使得装入背包中的物品

/ 的总价值最大？

/ 注：在选择装入背包的物品时，对物品i只有两种选择，

/ 即装入或不装入背包。不能将物品i装入多次，也

/ 不能只装入部分的物品i。

/

/ 1 0-1背包问题的形式化描述：

/ 给定c>0, wi>0, vi>0, 0<=i<=n，要求找到一个n元的

/ 0-1向量(x1, x2, , xn), 使得：

/ max sum_{i=1 to n} (vixi),且满足如下约束：

/ (1) sum_{i=1 to n} (wixi) <= c

/ (2) xi∈{0, 1}, 1<=i<=n

/

/ 2 0-1背包问题的求解

/ 0-1背包问题具有最优子结构性质和子问题重叠性质，适于

/ 采用动态规划方法求解

/

/ 21 最优子结构性质

/ 设(y1,y2,,yn)是给定0-1背包问题的一个最优解，则必有

/ 结论，(y2,y3,,yn)是如下子问题的一个最优解：

/ max sum_{i=2 to n} (vixi)

/ (1) sum_{i=2 to n} (wixi) <= c - w1y1

/ (2) xi∈{0, 1}, 2<=i<=n

/ 因为如若不然，则该子问题存在一个最优解(z2,z3,,zn)，

/ 而(y2,y3,,yn)不是其最优解。那么有：

/ sum_{i=2 to n} (vizi) > sum_{i=2 to n} (viyi)

/ 且，w1y1 + sum_{i=2 to n} (wizi) <= c

/ 进一步有：

/ v1y1 + sum_{i=2 to n} (vizi) > sum_{i=1 to n} (viyi)

/ w1y1 + sum_{i=2 to n} (wizi) <= c

/ 这说明：(y1,z2,z3,zn)是所给0-1背包问题的更优解，那么

/ 说明(y1,y2,,yn)不是问题的最优解，与前提矛盾，所以最优

/ 子结构性质成立。

/

/ 22 子问题重叠性质

/ 设所给0-1背包问题的子问题 P(i,j)为：

/ max sum_{k=i to n} (vkxk)

/ (1) sum_{k=i to n} (wkxk) <= j

/ (2) xk∈{0, 1}, i<=k<=n

/ 问题P(i,j)是背包容量为j、可选物品为i,i+1,,n时的子问题

/ 设m(i,j)是子问题P(i,j)的最优值，即最大总价值。则根据最优

/ 子结构性质，可以建立m(i,j)的递归式：

/ a 递归初始 m(n,j)

/ //背包容量为j、可选物品只有n，若背包容量j大于物品n的

/ //重量，则直接装入；否则无法装入。

/ m(n,j) = vn, j>=wn

/ m(n,j) = 0, 0<=j<wn

/ b 递归式 m(i,j)

/ //背包容量为j、可选物品为i,i+1,,n

/ //如果背包容量j<wi，则根本装不进物品i，所以有：

/ m(i,j) = m(i+1,j), 0<=j<wi

/ //如果j>=wi，则在不装物品i和装入物品i之间做出选择

/ 不装物品i的最优值：m(i+1,j)

/ 装入物品i的最优值：m(i+1, j-wi) + vi

/ 所以：

/ m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi

/

//

#define max(a,b) (((a) > (b)) (a) : (b))

#define min(a,b) (((a) < (b)) (a) : (b))

template <typename Type>

void Knapsack(Type v, int w, int c, int n, Type m)

{

//递归初始条件

int jMax = min(w[n] - 1, c);

for (int j=0; j<=jMax; j++) {

m[n][j] = 0;

}

for (j=w[n]; j<=c; j++) {

m[n][j] = v[n];

}

//i从2到n-1，分别对j>=wi和0<=j<wi即使m(i,j)

for (int i=n-1; i>1; i--) {

jMax = min(w[i] - 1, c);

for (int j=0; j<=jMax; j++) {

m[i][j] = m[i+1][j];

}

for (j=w[i]; j<=c; j++) {

m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);

}

}

m[1][c] = m[2][c];

if (c >= w[1]) {

m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);

}

}

template <typename Type>

void TraceBack(Type m, int w, int c, int n, int x)

{

for (int i=1; i<n; i++) {

if(m[i][c] == m[i+1][c]) x[i] = 0;

else {

x[i] = 1;

c -= w[i];

}

}

x[n] = (m[n][c]) 1:0;

}

int main(int argc, char argv[])

{

int n = 5;

int w[6] = {-1, 2, 2, 6, 5, 4};

int v[6] = {-1, 6, 3, 5, 4, 6};

int c = 10;

int ppm = new int[n+1];

for (int i=0; i<n+1; i++) {

ppm[i] = new int[c+1];

}

int x[6];

Knapsack<int>(v, w, c, n, ppm);

TraceBack<int>(ppm, w, c, n, x);

return 0;

}

二贪心算法求解0-1背包问题

1贪心法的基本思路：

——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：

1)不能保证求得的最后解是最佳的；

2)不能用来求最大或最小解问题；

3)只能求满足某些约束条件的可行解的范围。

实现该算法的过程：

从问题的某一初始解出发；

while 能朝给定总目标前进一步 do

求出可行解的一个解元素；

由所有解元素组合成问题的一个可行解；

2例题分析

1)[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品 A B C D E F G

重量 35 30 60 50 40 10 25

价值 10 40 30 50 35 40 30

分析：

目标函数： ∑pi最大

约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？

（2）每次挑选所占空间最小的物品装入是否能得到最优解？

（3）每次选取单位容量价值最大的物品，成为解本题的策略。

<程序代码:>(环境:c++)

#include<iostreamh>

#define max 100 //最多物品数

void sort (int n,float a[max],float b[max]) //按价值密度排序

{

int j,h,k;

float t1,t2,t3,c[max];

for(k=1;k<=n;k++)

c[k]=a[k]/b[k];

for(h=1;h<n;h++)

for(j=1;j<=n-h;j++)

if(c[j]<c[j+1])

{t1=a[j];a[j]=a[j+1];a[j+1]=t1;

t2=b[j];b[j]=b[j+1];b[j+1]=t2;

t3=c[j];c[j]=c[j+1];c[j+1]=t3;

}

}

void knapsack(int n,float limitw,float v[max],float w[max],int x[max])

{float c1; //c1为背包剩余可装载重量

int i;

sort(n,v,w); //物品按价值密度排序

c1=limitw;

for(i=1;i<=n;i++)

{

if(w[i]>c1)break;

x[i]=1; //x[i]为1时，物品i在解中

c1=c1-w[i];

}

}

void main()

{int n,i,x[max];

float v[max],w[max],totalv=0,totalw=0,limitw;

cout<<"请输入n和limitw:";

cin>>n >>limitw;

for(i=1;i<=n;i++)

x[i]=0; //物品选择情况表初始化为0

cout<<"请依次输入物品的价值："<<endl;

for(i=1;i<=n;i++)

cin>>v[i];

cout<<endl;

cout<<"请依次输入物品的重量："<<endl;

for(i=1;i<=n;i++)

cin>>w[i];

cout<<endl;

knapsack (n,limitw,v,w,x);

cout<<"the selection is:";

for(i=1;i<=n;i++)

{

cout<<x[i];

if(x[i]==1)

totalw=totalw+w[i];

}

cout<<endl;

cout<<"背包的总重量为："<<totalw<<endl; //背包所装载总重量

cout<<"背包的总价值为："<<totalv<<endl; //背包的总价值

}

三回溯算法求解0-1背包问题

10-l背包问题是子集选取问题。

一般情况下，0-1背包问题是NP难题。0-1背包

问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类

似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当

右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余

物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+r≤bestp时，可剪去右

子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后

依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是

右子树中解的上界。

2解决办法思路：

为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考

察各物品即可。在实现时，由bound计算当前结点处的上界。在搜索解空间树时，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。

2算法框架：

a问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。

b回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

3运用回溯法解题通常包含以下三个步骤：

a针对所给问题，定义问题的解空间；

b确定易于搜索的解空间结构；

c以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；

#include<iostream>

using namespace std;

class Knap

{

friend int Knapsack(int p[],int w[],int c,int n );

public:

void print()

{

for(int m=1;m<=n;m++)

{

cout<<bestx[m]<<" ";

}

cout<<endl;

};

private:

int Bound(int i);

void Backtrack(int i);

int c;//背包容量

int n; //物品数

int w;//物品重量数组

int p;//物品价值数组

int cw;//当前重量

int cp;//当前价值

int bestp;//当前最优值

int bestx;//当前最优解

int x;//当前解

};

int Knap::Bound(int i)

{

//计算上界

int cleft=c-cw;//剩余容量

int b=cp;

//以物品单位重量价值递减序装入物品

while(i<=n&&w[i]<=cleft)

{

cleft-=w[i];

b+=p[i];

i++;

}

//装满背包

if(i<=n)

b+=p[i]/w[i]cleft;

return b;

}

void Knap::Backtrack(int i)

{

if(i>n)

{

if(bestp<cp)

{

for(int j=1;j<=n;j++)

bestx[j]=x[j];

bestp=cp;

}

return;

}

if(cw+w[i]<=c) //搜索左子树

{

x[i]=1;

cw+=w[i];

cp+=p[i];

Backtrack(i+1);

cw-=w[i];

cp-=p[i];

}

if(Bound(i+1)>bestp)//搜索右子树

{

x[i]=0;

Backtrack(i+1);

}

}

class Object

{

friend int Knapsack(int p[],int w[],int c,int n);

public:

int operator<=(Object a)const

{

return (d>=ad);

}

private:

int ID;

float d;

};

int Knapsack(int p[],int w[],int c,int n)

{

//为Knap::Backtrack初始化

int W=0;

int P=0;

int i=1;

Object Q=new Object[n];

for(i=1;i<=n;i++)

{

Q[i-1]ID=i;

Q[i-1]d=10p[i]/w[i];

P+=p[i];

W+=w[i];

}

if(W<=c)

return P;//装入所有物品

//依物品单位重量排序

float f;

for( i=0;i<n;i++)

for(int j=i;j<n;j++)

{

if(Q[i]d<Q[j]d)

{

f=Q[i]d;

Q[i]d=Q[j]d;

Q[j]d=f;

}

}

Knap K;

Kp = new int[n+1];

Kw = new int[n+1];

Kx = new int[n+1];

Kbestx = new int[n+1];

Kx[0]=0;

Kbestx[0]=0;

for( i=1;i<=n;i++)

{

Kp[i]=p[Q[i-1]ID];

Kw[i]=w[Q[i-1]ID];

}

Kcp=0;

Kcw=0;

Kc=c;

Kn=n;

Kbestp=0;

//回溯搜索

KBacktrack(1);

Kprint();

delete [] Q;

delete [] Kw;

delete [] Kp;

return Kbestp;

}

void main()

{

int p;

int w;

int c=0;

int n=0;

int i=0;

char k;

cout<<"0-1背包问题——回溯法 "<<endl;

cout<<" by zbqplayer "<<endl;

while(k)

{

cout<<"请输入背包容量(c)："<<endl;

cin>>c;

cout<<"请输入物品的个数(n)："<<endl;

cin>>n;

p=new int[n+1];

w=new int[n+1];

p[0]=0;

w[0]=0;

cout<<"请输入物品的价值(p)："<<endl;

for(i=1;i<=n;i++)

cin>>p[i];

cout<<"请输入物品的重量(w)："<<endl;

for(i=1;i<=n;i++)

cin>>w[i];

cout<<"最优解为(bestx)："<<endl;

cout<<"最优值为(bestp)："<<endl;

cout<<Knapsack(p,w,c,n)<<endl;

cout<<"[s] 重新开始"<<endl;

cout<<"[q] 退出"<<endl;

cin>>k;

}

四分支限界法求解0-1背包问题

1问题描述：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。

2设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。

#include <iostreamh>

struct good

{

int weight;

int benefit;

int flag;//是否可以装入标记

};

int number=0;//物品数量

int upbound=0;

int curp=0, curw=0;//当前效益值与重量

int maxweight=0;

good bag=NULL;

void Init_good()

{

bag=new good [number];

for(int i=0; i<number; i++)

{

cout<<"请输入第件"<<i+1<<"物品的重量:";

cin>>bag[i]weight;

cout<<"请输入第件"<<i+1<<"物品的效益:";

cin>>bag[i]benefit;

bag[i]flag=0;//初始标志为不装入背包

cout<<endl;

}

}

int getbound(int num, int bound_u)//返回本结点的c限界和u限界

{

for(int w=curw, p=curp; num<number && (w+bag[num]weight)<=maxweight; num++)

{

w=w+bag[num]weight;

p=w+bag[num]benefit;

}

bound_u=p+bag[num]benefit;

return ( p+bag[num]benefit((maxweight-w)/bag[num]weight) );

}

void LCbag()

{

int bound_u=0, bound_c=0;//当前结点的c限界和u限界

for(int i=0; i<number; i++)//逐层遍历解树决定是否装入各个物品

{

if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍历左子树

upbound=bound_u;//更改已有u限界,不更改标志

if( getbound(i, &bound_u)>bound_c )//遍历右子树

//若装入，判断右子树的c限界是否大于左子树根的c限界，是则装入

{

upbound=bound_u;//更改已有u限界

curp=curp+bag[i]benefit;

curw=curw+bag[i]weight;//从已有重量和效益加上新物品

bag[i]flag=1;//标记为装入

}

}

}

void Display()

{

cout<<"可以放入背包的物品的编号为：";

for(int i=0; i<number; i++)

if(bag[i]flag>0)

cout<<i+1<<" ";

cout<<endl;

delete []bag;

}

决策树，是要你做出分析重点是在结果，也就是说，你要执行一项案例最终的决定和结果确认。动态规划，就是在你策划事情和项目中，要准备有多路选择，就像我们做任体务，一样，要有灵活性，做了这个计划，还要想到有可能变动的可能，有后路，网络计划，就是，你要分支关系网，很灵活的将你的工作分配好，不会因为许多工作内容有一条出问题而堵住，合理的分配网络支点。

max Z=4x1+5x2 +6x3

st 3x1+4x2+5x3<=10

x1,x2,x3>=0且都为整数

约束条件分析：

x1=1,2,3

x2=1,2

x3=1,2

阶段变量：x1、x2、x3

状态变量：

决策变量：

目标函数：Z=4x1+5x2 +6x3

状态转移方程：

约束条件用惩罚处理

……未完待续……

以上就是关于200分求动态规划详解！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！全部的内容，包括:200分求动态规划详解！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！、动态规划中的0-1背包问题怎么去理解要求给出具体实例和详细步骤。。。、什么是动态规划等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！