动态规划

动态规划介绍

  动态规划比较适合用来求解最优问题，比如求最大值、最小值等等; 与回溯算法相同的是都会分多级进行计算, 不同的是会对每一级进行合并统计.

  非常典型的, 对于0-1背包问题在指定重量下求取可以获得的最大重量: 无论回溯算法还是动态规划都对每一个物品是否放入和不放入继续判断, 回溯算法往往继续递归将此级获得的信息传给下一级, 每个递归中这些信息都可能不同; 动态规划则对信息做一个记录统计比如说保存在数组中, 然后直接在这个数组上推算下一级.

动态规划0-1背包问题解法说明

假设: 每个物品的重量分别是 2,2,4,6,3, 物品个数为n=5, 允许重量w=9

• 1 建立一个n*w(物品个数*重量)的数组, 那么对于第一级来说我们可以得到: data[0][2]=data[0][0]=true两种情况
• 2 对于第二级, 我们可以得到: data[1][0+0]=data[1][0+2]=data[1][2+0]=data[2+2]=true三种情况
• 3 依次进行, 我们就可以在一个数组中保存所有的可能情况了
• 4 同时我们需要注意的是: data[n-1]的数据仅仅被data[n]用到此后均不需要, 我们甚至不需要n*w的空间

-	0	1	2	3	4	5	6	7	8	9
0	1	0	1	0	0	0	0	0	0	0
0	1	0	1	0	1	0	0	0	0	0

C++解法说明

void knapsack2(int *item, int n, int w)
{
    bool *state = new bool[w+1];
    for(int i = 0; i < w; i++)
    {
        state[i] = false;
    }

    state[0] = true;
    if(item[0] <= w) state[item[0]] = true;

    for(int i = 1; i < n; i++)
    {
        for(int j = w - item[i]; j >= 0; j--)
        {
            if(state[j])    state[j+item[i]] = true;
        }
    }

    for(int i = w; i >= 0; i--)
    {
        if(state[i])
        {
            printf("weight: %d\n", i);
            break;
        }
    }
}

动态规划问题的特征

LeetCode-120-三角形的最小路径和, 举例说明!

• 1 后续阶段的状态信息可以通过前一阶段推算出来
• 2 当某一阶段的状态确定后, 就不必关系之前的状态; 也不会被后续状态影响.
• 3 状态合并, 优于回溯算法的重要优点就是能够去掉很多重复的子问题(或者不必要判断的子问题)
• 4 状态转移方程: 最重要的一点是我们需要找到一个方程能够将上一级状态转变为下一级, 可以见举例中的: 解题思路.

强烈建议, 结合例子看动态规划的理论!