动态规划算法是一种经典的算法

动态规划算法是一种经典的算法，它是如此美妙的算法，值得每一个程序员拥有。但是，直到晚上看《算法导论》，才发现自己现在才全面理解它，不禁狂汗。。。

以经典的背包问题来展示动态规划算法：

代码

1 #include

2

3 #define N 4

4 #define W 5

5

6 //物品的重量

7 int w[] = {-1, 2, 1, 3, 2};

8

9 //价值数组

10 int vi[] = {-1, 12, 10, 20, 15};

11

12 int v[N+1][W+1]; //v[i][j]表示从前i个物品选能够放进承重量为j的背包的子集的最大总价值

13

14 void init()

15 {

16 int i, j;

17 for (i = 0; i <= N; i++)

18 for (j = 0; j <= W; j++)

19 v[i][j] = -1;

20

21 for (i = 0; i <= N; i++)

22 v[i][0] = 0;

23

24 for (i=0; i <= W; i++)

25 v[0][i] = 0;

26 }

27

28

29 //基于备忘录的动态规划算法

30 int MKFnapsack_MEMOIZE(int i, int j)

31 {

32 int value;

33 if (v[i][j] < 0) //如果v[i][j]还没有计算,则进行计算

34 {

35 if (j < w[i])

36 value = MKFnapsack_MEMOIZE(i-1,j);

37 else

38 {

39 int v1 = MKFnapsack_MEMOIZE(i-1, j);

40 int v2 = MKFnapsack_MEMOIZE(i-1, j-w[i]) + vi[i];

41 value = v1 >=v2 ? v1:v2;

42 }

43 v[i][j] = value;

44 }

45 return v[i][j]; //如果v[i][j]已经进行计算,则不进行计算,直接返回即可

46 }

47

48 //自顶向下的动态规划算法

49 int MKFnapsack_TOP_TO_BOTTOM(int i, int j)

50 {

51 int value;

52

53 if(i <= 0 || j <= 0)

54 return 0;

55

56 //不管v[i][j]是否计算过,都进行计算

57 if (j < w[i])

58 value = MKFnapsack_TOP_TO_BOTTOM(i-1, j);

59 else

60 {

61 int v1 = MKFnapsack_TOP_TO_BOTTOM(i-1, j);

62 int v2 = MKFnapsack_TOP_TO_BOTTOM(i-1, j-w[i]) + vi[i];

63 value = v1 >= v2 ? v1:v2;

64 }

65

66 return value;

67 }

68

69 //自底向上的算法

70 int MKFnapsack_BOTTOM_TO_TOP(int Ni, int Wi)

71 {

72 int i, j;

73 for (i = 1; i <= Ni; i++)

74 {

75 for(j = 1; j <= Wi; j++)

76 {

77 if(j < w[i])

78 v[i][j] = v[i-1][j];

79 else //j >=w[i]

80 {

81 int v1= v[i-1][j];

82 int v2 = v[i-1][j-w[i]] + vi[i];

83 v[i][j] = v1 >= v2 ? v1:v2;

84 }

85 }

86 }

87 return v[N][W];

88 }

89

90 void print_v(int Ni, int Wi)

91 {

92 int i, j;

93 for(i = 0; i <= Ni; i++)

94 {

95 for(j = 0; j <= Wi; j++)

96 printf(\"%d \", v[i][j]);

97 printf(\"\\n\");

98 }

99 }

100

101 int main()

102 {

103 printf(\"top to bottom most value is:%d\\n\", MKFnapsack_TOP_TO_BOTTOM(N, W));

104

105 init();//数组初始化

106 printf(\"memoize most value is:%d\\n\", MKFnapsack_MEMOIZE(N, W));

107 print_v(N, W);

108

109 init();

110 printf(\"bottom to top most value is:%d\\n\", MKFnapsack_BOTTOM_TO_TOP(N, W));

111 print_v(N, W);

112

113 return 0;

114 }

输出结果：

自顶向下的递归算法，写法最简单，但效率是最低的，它往往把问题搞成指数级。而自底向上的算法是DP的经典策略，它比自顶向下的效率高，但是，它往往也计算了没有必要计算的子问题(见上图)。而基于备忘录的自顶向下的算法是前两者的集大成者，效率最优。

出师表

两汉：诸葛亮

先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋也。然侍卫之臣不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。诚宜开张圣听，以光先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。

宫中府中，俱为一体；陟罚臧否，不宜异同。若有作奸犯科及为忠善者，宜付有司论

其刑赏，以昭陛下平明之理；不宜偏私，使内外异法也。

侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：愚以为宫中之事，事无大小，悉以咨之，然后施行，必能裨补阙漏，有所广益。

将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰“能”，是以众议举宠为督：愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。

亲贤臣，远小人，此先汉所以兴隆也；亲小人，远贤臣，此后汉所以倾颓也。先帝在时，每与臣论此事，未尝不叹息痛恨于桓、灵也。侍中、尚书、长史、参军，此悉贞良死节之臣，愿陛下亲之、信之，则汉室之隆，可计日而待也。

臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。先帝不以臣卑鄙，猥自枉屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。后值倾覆，受任于败军之际，奉命于危难之间，尔来二十有一年矣。

先帝知臣谨慎，故临崩寄臣以大事也。受命以来，夙夜忧叹，恐托付不效，以伤先帝之明；故五月渡泸，深入不毛。今南方已定，兵甲已足，当奖率三军，北定中原，庶竭驽钝，攘除奸凶，兴复汉室，还于旧都。此臣所以报先帝而忠陛下之职分也。至于斟酌损益，进尽忠言，则攸之、祎、允之任也。

愿陛下托臣以讨贼兴复之效，不效，则治臣之罪，以告先帝之灵。若无兴德之言，则责攸之、祎、允等之慢，以彰其咎；陛下亦宜自谋，以咨诹善道，察纳雅言，深追先帝遗诏。臣不胜受恩感激。

今当远离，临表涕零，不知所言。