概述

动态规划（英语：Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

三大性质

最优子结构性质
如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

子问题重叠性质
子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

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

规律

这样的规律前人已经给我们总结好了，我们瞬间都能站在巨人的肩膀上呢。下面是我画的前人已经总结好的规律，总是认为画一遍就有一遍的印象。

C# Demo

如下是自己写的代码，不过仍在完善中，不断的更新，不断的装饰。

private void button1_Click(object sender, EventArgs e)        {            //物品容量和价值的对应            int[] value=new int[5]{
  4,5,10,11,13};            int[] weight=new int[5]{
  3,4,7,8,9};            int c = DynamicProgram(17, 5, weight, value);            label1.Text = "最大价值为" + c.ToString();// +"\r\n" + "物品编号为：" + "1,2,3,4,5" + "\r\n" + "物品状态为：";        }        //0-1背包问题，动态规划        //核心思想        /*1.当没有物品，或没有包时，总价值为0         * 2.当物品放不进包时，最优总价值和当前物品无关系         * 3.当物品容量比剩余容量小的时候，考虑放不放两种情况         */        public int DynamicProgram(int W, int n, int[] weigth, int[] value)        {                     //剩余容量            int w;            //物品编号i;            int i;            //i个物品导致的背包的剩余容量为w的，最优的总价值 c(i,w)            int[,] c = new int[n+1, W+1];  //&#&这里加1是因为：容量包含0   ；  n是个数，个数增加1是因为：个数包含0            //没有物品可放时            for (w=0; w<=W; w++)            {               c[0,w]=0;            }            //背包中有物品时            for ( i = 1; i <= n; i++)            {                c[i,0] = 0;                for (w= 1; w<=W; w++)                {                    if (weigth[i-1]<=w) //当物品在包中，状态:1                    {                        c[i,w] = Max(c[i-1,w-weigth[i-1]]+value[i-1],c[i-1,w]);                    }                    else                    {                        c[i,w] = c[i - 1,w];                    }                }            }            return c[n, W];        }        //取最大值函数        public int Max(int i,int w) {            if (i> w)            {                return i;             }            else            {                return w;            }        }

one for all 。。。

近期在研究算法，后续也会有陆陆续续的更上。希望路过的小伙伴，多给建议，我们一起成长。

你可能感兴趣的文章