一.动态规划原理

多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

设计动态规划具体要满足以下三个条件：

1.最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
3.子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

动态规划是一门思想，可以引用于很多比较复杂的解决方案中，我个人给他做的定位就是

1.空间换时间
2.解决问题由小到大，就片面到全面
 
下面将从几个例子作为切入点，如果对问题进行动态规划

二.数字三角形

如图，从9开始往下走，每次只能走相邻的两个节点，问如果走才能使数字之和最大化。

这个问题如果采用遍历的方式那么路径将会呈指数级别增长,计算量非常大
20 x 21 x 22 ….x 2n-1 = 2 n(n-1) / 2

如果采用贪婪算法每次选择最大值 ,到达第四层的时候:9+15+8+9 < 9+12+10+18。这种方式只能得到局部最优解，而无法得到全局最优解。

显然这两种方式都不是最优的解决方式。如果采用DP(动态规划)可以有效解决。

具体思想：我们从最底层往上走，从5五层到第四层开始比较，选择最大的值：分别为19+2，18+10，9+10，5+16.然后基于这4个值继续比较从第4层往第三层走，最后第三层变为18+10+10，18+10+6，5+16+8.按照这种思路依次走到第一层。

这样保证了，从第5层开始，每一次抉择后的结构都是最优的结果，并且再也不会收到其他因素的音响值不会改变，且有由小到大最终每一个点的连线其实都是自他开始往下的最优解。
刚好满足了DP算法的三个特性:
1.最优化原理 2.无后向性 3子问题重叠

测试数据和代码如下：

int array[5][5] = {
    7,0,0,0,0,
    3,8,0,0,0,
    8,1,0,0,0,
    2,7,4,4,0,
    4,5,2,6,5,
};

//动态划分
for (int i = 4 - 1; i >= 0; i--) {
   for (int j = 0; j <= 4; j++) {
       array[i][j] = MAX(array[i + 1][j] , array[i+1][j+1]) + array[i][j];
    }
}
NSLog(@"结果%d",array[0][0]);

 

三.01背包

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

 

DP思想如下：拆分结构，寻找最优子元素。  最大结构是5个物品中寻找重量和为10且价值最大的物品，那么最优子结构就是从1个物品选出重量和为1且价值最大的元素，如果条件满足则就是他本身，不满足则记为0，然后再一次往上递增。

含义 name weight value 1kg 2kg 3kg 4kg 5kg 6kg 7kg 8kg 9kg 10kg
abcde可选 a 2 6 0 6 6 9 9 12 12 15 15 15（结束）
bcde可选 b 2 3 0 3 3 6 6 9 9 9 10 11
cde可选 c 6 5 0 0 0 6 6 6 6 6 10 11
de可选 d 5 4 0 0 0 6 6 6 6 6 10 10
e可选 e 4 6 0（开始） 0 0 6 6 6 6 6 6 6 

 表格填写的顺序是从左下开始填写直到右上结束，如果这个表格你能手动填写完，那么你就已经学会了01背包规划方案。

 为了方便理解，我们选择几个典型的进行描述：

表格从白色部分开始数

第5行第2列（e2）:可选物只有e,且有一个负重为2的背包，背包的最大价值为0，因为e本身的重量为4，放不下，这个表格故填0.

第2行第2列（b2）:可选物为b,c,d,e,且有一个负重为2的背包，背包最大价值为3，因为物品b重量为2刚好可以放下且价值为3，表格填3.

第1行第2列（a2）:可选物为a,b,c,d,e，且有一个负重为2的背包,背包最大价值为6，a和b都可以放入背包，且a的价值更大，选择a，表格填6.

第1行第4列（a4）:可选物a,b,c,d,e， 且有一个负重为4的背包，a可以装下，那么到底装不装如a呢？我们需要做一个比较，假如装下a，背包剩余负重2，可选物为b,c,d,e,   (b2)+6=9大于b4,选择装入a更好，所以a4的填入9。

第1行第5列（a6）:装入a后剩余重量为4，可选b,c,d,e.  b(4)+6=12 > b6所以填入12.

 

若 f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。Pi表示第i件物品的价值，Wi表示第i件物品的重量，01背包核心方程式为：
 f[i,j] = Max{ f[i-1,j-Wi] + Pi( j >= Wi ) ,  f[i-1,j]  }

核心代码如下：

 

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    
    //背包能装入的总重量为10  5个物品的重量分别为2，2，6，5，4  价值为6，3，5，4，9
    int knapsackSize = 10;
    MyItem * item1 = [MyItem myitemWithWeight:2 value:6];
    MyItem * item2 = [MyItem myitemWithWeight:2 value:3];
    MyItem * item3 = [MyItem myitemWithWeight:6 value:5];
    MyItem * item4 = [MyItem myitemWithWeight:5 value:4];
    MyItem * item5 = [MyItem myitemWithWeight:4 value:9];
    NSArray* myitems = @[item1,item2,item3,item4,item5];
    
    int value = [self getValueByKnapsack:myitems knapsackSize:knapsackSize];
    NSLog(@"背包可装入的最大价值%d",value);
}

//计算01背包能装入的价格最优的值  MyItem（有两个属性value和weight） 可以用于被装的元素  size背包一共能载重多少
-(int)getValueByKnapsack:(NSArray<MyItem *> *)myitems knapsackSize:(int)knapsackSize {
    //初始化一个 二维表格记录每个最优策略的值  空间换时间 行数为总元素个数  列数为背包从0开始到总重量数
    int ** a;
    a = (int **)malloc(sizeof(int *) * myitems.count);
    for (int i = 0; i < myitems.count; i++) {
        a[i] = (int *)malloc(sizeof(int) * knapsackSize + 1);
        a[i][0] = 0;
    }
    
    //最优子元素从只装1个元素且载重只为1开始计算,保证最优子元素且无后向性
    //遍历重量从假如背包只能载重1的策略开始
    for (int i = 1; i <= knapsackSize; i ++) {
        //可选物品从 0 到 所有
        for (int j = 0; j < myitems.count; j++) {
            MyItem * item = myitems[j];
            
            if (i < item.weight) {
                //背包装不下的情况
                if (j == 0) {
                    //只有一个可选数据时
                    a[j][i] = 0;
                }
                else {
                    //有多个可选数据 则使用上一个最优策略
                    a[j][i] = a[j-1][i];
                }
            }
            else {
                //背包装的下的情况
                if (j == 0) {
                    //只有一个可选数据 这个数据记录为最优策略
                    a[j][i] = item.value;
                }
                else {
                    //有多个可选择的物品 则和上一个最优策略比较选择最优策略
                    a[j][i] = MAX(a[j - 1][i], item.value + a[j - 1][i - item.weight]);
                }
            }
        }
    }
    
    //查询最大值
    int maxValue = 0;
    for (int i = 1; i <= knapsackSize; i ++) {
        for (int j = 0; j < myitems.count; j ++) {
            if (a[j][i] > maxValue) {
                maxValue = a[j][i];
            }
        }
    }
    
    return maxValue;
    
}

 

 

拓展：

最后再拓展一个小问题，你可以先不看思路尝试着自己用动态划分的思想解决。

对于一个从1到N的连续整数集合{1,2,3……,n-1,n},划分为两个子集，保证两个集合的和相等。

例：n=3可分为{1,2}and{3}.  如果n=7可分为  {1,6,7} and {2,3,4,5}    {2,5,7} and {1,3,4,6}    {3,4,7} and {1,2,5,6}    {1,2,4,7} and {3,5,6}

设计一个程序 输入任意数划分出可行的方案数，不能划分则输出0. 

 

 

 

 

 

 

思路如下：

1+2+3…..+n = n*(n+1)/2,  两个相同的子集任意一个的和肯定为总数和的一半，顾和一定为n*(n+1)/4，计作f(n).  所以这个题可以转化为从集合中找出和为f(n)的子集合的数量，将他除以2就是我们可以得到的划分方案。   这样又可以用01背包的思想再次转换，就成了背包问题了。物品1,2,3……,n， 价值分别为1,2,3……,n.给定一个称重为f(n)的背包，问一共有多少种方案让其刚好放满，最后将方案除以2就是真确结果。
表格划分如下：

 

  

版权声明：本文为xiaolong-原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：http://www.cnblogs.com/xiaolong-/p/8029381.html