典例浅析动态规划(dynamic programming)

动态规划即为将大问题分为小问题解决，并最终利用小问题的解运作出最终问题的解。

其精髓在于绘制一个二维的表格，这里介绍动态规划最简单的例题——背包问题。

题目：有一个4磅限重的背包，要求尽可能装价值更高的商品。
商品信息：音响 3000元 4磅
笔记本电脑 2000元 3磅
吉他 1500元 1磅
iphone 2000元 1磅

解法（含注释）：

int main()
{
    int n=4, v=4;/** n代表商品数量 v代表背包限重 */
    int weight[5]={0, 4, 3, 1, 1}, value[5]={0, 3000, 2000, 1500, 2000};/** weight表示商品重量，value表示商品价值，注意索引0项初值0*/
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= v;j++)/**开始建表，填完每个重量阈值后更换商品*/
        {
            if(j >= weight[i])/**如果背包可放该商品，则做如下比较*/
            f[i][j] = max(f[i-1][j-weight[i]] + value[i] ,f[i-1][j]);/**将当前商品价值+剩余空间价值与同限重上一行背包的价值比较并更新*/
            //else
            //f[i][j] = f[i-1][j];
        }
    }
    cout << f[n][v] << endl;/**输出*/
}

图片形式：

实际题目会比该例题难度大很多，注意优化和题目陷阱