原创 进阶算法概述

二.动态规划

1.算法本质

• 状态

一个方程，用于表述问题的(1-n)通向公式，可以是求解过程中一个开始或一个结果

• 状态转移方程

状态与状态的关系公式，就是转移方程,比如状态k和状态k-1

2.解题步骤

• 二维数组填表

状态与状态的转移用一张二维表来表述，通过双重循环来逐渐把二维表填满，表每一行是一个状态，下一行是转移到另一个状态，最终填满二维表

3.例题

3.1 0-1背包问题

• 问题描述

有N件物品和一个容量为==v==的背包。第i件物品的重量是==c[i]==(每一件物品只有一件，可以选择装或者不装，也就是问题0-1的意思)，价值是==w[i]==。求解将哪些物品装入背包可使价值总和最大。

• 状态

即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。

• 转移方程

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

• 伪代码

#c[i]=cost[i],w[i]=weight[i]
for i=1..N

    for v=V..0

        f[v]=max{f[v],f[v-c[i]]+w[i]};

3.2 TSP问题

• 问题描述

Travelling Salesman Problem (TSP) 是最基本的路线问题。它寻求的是旅行者由起点出发，通过所有给定的需求点后，再次返回起点所花费的最小路径成本

• 状态

d(i,v)表示从顶点i出发，经过v中所有结点一次后的最小花费

• 转移方程

$d(i,v)=min_{i\epsilon{v}}\{d(k,v)+c_{ki}\}$

• 代码

for(int j=1;j<1<<(n-1);j++){
            for(int i=1;i<n;i++){    //j用二进制表示的城市集合
                    if(((1<<(i-1))&j)==0){         //i不在j表示的城市集合中

                        minDis=60000;
                        for(int k=1;k<n;k++){
                        if(((1<<(k-1))&j)!=0)  {//k表示的城市在j表示的城市集合中

                        temp=dis[i][k]+d[k][j-(1<<(k-1))];
                        if(temp<minDis){
                            minDis=temp;   //所有k中最小的距离
                        }
                        }
                        }
                    }
                    d[i][j]=minDis;
            }
        }

其他

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

• 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
• 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。
• 如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。