动态规划算法是一种经典的算法，它是如此美妙的算法，值得每一个程序员拥有。但是，直到晚上看《算法导论》，才发现自己现在才全面理解它，不禁狂汗。。。 以经典的背包问题来展示动态规划算法： 代码
1 #include
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(\, v[i][j]); 97 printf(\); 98 } 99 } 100
101 int main() 102 {
103 printf(\, MKFnapsack_TOP_TO_BOTTOM(N, W)); 104
105 init();//数组初始化
106 printf(\, MKFnapsack_MEMOIZE(N, W)); 107 print_v(N, W); 108
109 init();
110 printf(\, MKFnapsack_BOTTOM_TO_TOP(N, W));
111 print_v(N, W); 112
113 return 0; 114 }
输出结果：