关于动态规划法

概念

动态规划法离不开一个关键词,拆分 ,就是把求解的问题分解成若干个子阶段,前一问题的结果就是求解后一问题的子结构。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

适用性

适用动态规划的问题必须满足最优化原理和无后效性。

最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。

解题思路

1.确定最优子结构:比如我们要求的结果F(X)的最优子结构可能为F(X-1)和F(X-2)

2.列转移方程:根据最优子结构可以列出转移方程F(X)=F(X-1)+F(X-2)

3.确定边界值:确定问题的边界,即当F(n)有可以确定的具体的值

以上概述是纯粹是为了显得官方一点,下面我们开始说人话

开始说人话

动态规划法,规划的意思就是划分,求解一个问题时,把问题划分成多个子阶段,比如兔子繁殖问题,

有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问第n个月的兔子总数为多少?

对于这个问题,我们可以根据月份把问题划分为n个阶段,每个月的兔子数,都会等于前一个月的兔子数加上这个月新出生的兔子数,
所以 第n个月的兔子数=第n-1个月的兔子数+新出生的兔子数,
而 新出生的兔子数=有繁殖能力的兔子数=两个月前的兔子数,
即:第n个月的兔子数=第n-1个月的兔子数+第n-2个月的兔子数

所以我们可以知道,我们要求的问题F(n)的最优子结构就是F(n-1)和F(n-2) ——对应解题思路的确定最优子结构

接着我们可以列出求解的方程 F(n)=F(n-1)+F(n-2) ———-列转移方程

对于方程F(n) = F(n-1)+F(n-2) 我们发现 F(n-1)和F(n-2)的结果也不知道,但是我们可以用同样的计算方法去求,F(n-1)=F(n-2)+F(n-3)以此类推,但是F(n)的在当n等于多少的时候才有确定的值呢,F(1)=1,F(2) = 1,这两个就是F(n)的边界值; ——-确定边界值

然后我们很容易就能写出代码

int f(int n){
    if(n==1||n==2){
        return 1;
    }
    return f(n-1)+f(n-2);
}

这就是使用动态规划法解题的基本思路

确定最优子结构——》列转移方程——》确定边界值

上楼梯问题

一个楼梯有 10 级台阶,从下往上走,每跨一步只能向上迈 1 级或者 2 级台阶,请问一共有多少种走法?

解题思路:

要想走到第 10 级台阶,要么是先走到第 9 级,然后再迈一步 1 级台阶上去,要么是先走到第 8 级,然后一次迈 2 级台阶上去。
这样的话,走到 10 级台阶的走法数,就等于走到 9 级台阶的走法数,加上走到 8 级台阶的走法数。
F(10) = F(9) + F(8) ——-确定最优子结构
而且不光是 10 级台阶如此,走到任何一级台阶的走法数,都符合这个逻辑,因此就可以得出一个通用公式:
F(x) = F(x-1) + F(x-2) ——-列转移方程

其中上一级台阶的方式只有一种,而上两级台阶的方式有两种,得到F(1)=1,F(2)=2 —–找边界值

代码如下:

int F1(int n){
    if(n==1){
        return 1;
    }
    if(n==2){
        return 2;
    }
    return F1(n-1)+F1(n-2);
}

但是很容易发现,这个代码的时间复杂度是O(2^n),当n的值较大的时候,计算的需要很长的时间

我们可以对代码进行简单的处理

int F2(int n){
    if(n==1){
        return 1;
    }
    if(n==2){
        return 2;
    }
    int t1 = 1;
    int t2 = 2;
    int temp = 0;
    for(int i=3;i<=n;i++){
        temp = t1+t2;
        t1 = t2;
        t2 = temp;
    }
    return temp;
}

这样时间复杂度就降低了很多

兔子问题

同理,兔子繁殖问题,我们也可以对代码进行同样的处理

void F(int n){
    int[] i = new int[n];//兔子数
    int[] s;//有生育能力的兔子数
    i[0] = 1;
    int t = 0;
    for(int j = 0;j<n;j++){//j月份
        if(j>=2){
            t = i[j - 2];
        }
        if(j>=1){
            i[j]=i[j-1]+t;
        }
        System.out.println("第"+(j+1)+"个月份的兔子数:"+i[j]);
    }
}

01背包问题

01背包问题是动态规划法的经典问题

​ 有一个背包,可以装载重量为5kg的物品。
​ 有4个物品,他们的重量和价值如下。
​ 背包:载重5kg
​ 物品1
​ 重量: 1kg
​ 价值:¥3
​ 物品2
​ 重量:2kg
​ 价值:¥4
​ 物品3:
​ 重量: 3kg
​ 价值:¥5
​ 物品4
​ 重量:4kg
​ 价值:¥6
​ 那么请问,在不得超过背包的承重的情况下,将哪些物品放入背包,可以使得总价值最大?

总重量是5kg,从四个物品中选,我们要求的问题就是:F(5,4),

对于第四个物品就只有两种情况,我们可以选择选,或者是不选

不选的话就还是5kg,只从前面三个物品去选,F(5,3)

选的话就是还剩下1kg,从前面三个去选,F(1,3)

F(5,4) = max { F(1,3) + 6, F(5,3) }

所以我们列出转移方程:

F(W,N) =max { F(W-Wn, N-1) + Vn,F(W, N-1) } (w是重量,n是从前n个去选,Wn是第n个的重量,Vn是第n个的价值)

接下来就是找临界值了:

当重量只剩下0kg的时候,就没有能够选择的物品了,最大价值就是0,所以F(0,n)=0,

当只是剩下的重量大于0,但是已经遍历到从前1个物品中选择时,那么能选择的物品就只有第一个,最大价值就是3,即F(n,1)=3

具体代码如下:

static int F(int weight,int i,res[] resarr){//weight是重量,resarr保存的是物品重量和价值
    if(weight==0){
        return 0;
    }
    if(i==1){
        return 3;
    }
    if(weight<resarr[i].getWeight()){//如果第i个物品的质量大于总的重量,则直接从前i-1个物品中去选择
        return F(weight,i-1,resarr);
    }
    return Math.max(F(weight-resarr[i].getWeight(),i-1,resarr)+resarr[i].getValue(),F(weight,i-1,resarr));
}