动态规划算法

一、概念

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
比较有趣的一句话是：每个动态规划都从一个网格开始。

问题 ==> 子问题 ==> 子问题最优解 ==> 问题最优解

二、思路

1.分析最优解的性质，并刻画其结构特征。
2.递归的定义最优解。
3.以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。
4.根据计算最优值时得到的信息，构造问题的最优解。

三、特性

• 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
• 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
• 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

四、应用

0-1背包问题

题目：
给定n种物品和一个背包，物品i的重量为wi，价值为vi，背包的容量为c。问：应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

分析：
0-1背包问题

代码：

#include<stdio.h>
#define MAX 100

int n;              // 描述物品个数
int c;              // 描述背包容量
int value[MAX];     // 描述物品价值
int weight[MAX];    // 描述物品重量

int main() {
    // 初始赋值操作
    value[0] = 1500;
    value[1] = 3000;
    value[2] = 2000;
    weight[0] = 1;
    weight[1] = 4;
    weight[2] = 3; 
    c = 4;
    n = 3;

    // 构造最优解的网格:3行4列
    int maxValue[MAX][MAX];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < c; j++) {
            maxValue[i][j] = 0;
        }
    }   // end for

    // 填充网格
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= c; j++) {
            if (i == 0) {
                maxValue[i][j - 1] = (weight[i] <= j ? value[i] : 0);
            } else {
                int topValue = maxValue[i - 1][j - 1];  // 上一个网格的值
                int thisValue = (weight[i] <= j ?       // 当前商品的价值 + 剩余空间的价值
                        (j - weight[i] > 0 ? value[i] + maxValue[i - 1][j - weight[i]] : value[i])
                        : topValue);

                // 返回 topValue和thisValue中较大的一个
                maxValue[i][j - 1] = (topValue > thisValue ? topValue : thisValue);
            }   // end if
        }   // end inner for
    }   // end outer for

    // 打印结果二维数组maxValue
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < c; j++) {
            printf("%6d", maxValue[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}