动态规划--钢条切割问题

什么是动态规划

1. 动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。
2. 动态规划和分治法相似，都是通过组合子问题的解来求解原问题。
3. 分治法讲问题划分成互不相交的子问题，递归求解子问题，再将他们的解组合起来，求出原问题的解。
4. 与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。在这种情况下，分治算法会做出许多不必要的工作，它会反复的求解那些公共子问题。而动态规划算法对每个子子问题只求解一次，将结果保存到表格中，从而无需每次求解一个子子问题都要重新计算。

动态规划–钢条切割问题

假定我们知道某公司出售一段长度为 N 英寸的钢条的价格为pi(i=1,2,3….), 钢条长度为整英寸如图给出价格表的描
述（任意长度的钢条价格都有）

问题：给一段长度为n的钢条，问怎么切割，获得的收益最大rn?

考虑n = 4的时候

假如一个最优解把n段七个成了k段(1<=k<=n),那么最优切割方案：

最大收益（每一段求最优解的和）：

最大收益表

第一种求最优解方案

对于r n(n>=1),最优切割收益：

将切割方案分成下面几种

1. 不切割收益为pn
2. 将它切割成两半，切割成两半的情况有，对每种情况求最优解(1,n-1) (2,n-2) (3,n-3) (4,n-4)…(n-1,1)，对这两半分别求最优解，最优解的和就是当前情况的最优解

例子：给一段长度为5的钢条，问怎么切割，获得的收益最大r5?

1. 不切割收益为p5 = 10
2. 切成两半，所以可以先从第一个位置开始切，切成（1，4），对长度为1和长度为4的钢条求切割最优解，也就是求r1和r4，r1+r4就是切割第一个位置的最优解
3. 从第二个位置开始切，切成（2，3），对长度为 2 和长度为 3 的钢条求切割最优解，也就是求r2和r3，r2+r3就是切割第二个位置的最优解
4. 同理，求出所有切成两半的情况，比较哪一种情况收益最大，r5 = max(所有情况)
5. 缺点：因为要用两次递归求最优解，效率低，比如r2 + r3，需要求两次递归

第二种最优解方案

1. 我们从钢条的左边切下长度为 i 的一段，只对右边剩下长度为 n - i 的一段继续进行切割，对左边的不再切割。
2. 这样，不做任何切割的方案就是：当第一段长度为 n 的时候，收益为 pn,剩余长度为 0，对应的收益为 0。如果第一段长度为 i ,收益为pi
   

例子：给一段长度为5的钢条，问怎么切割，获得的收益最大r5?

1. 不切割，r5 = p5 = 10 （i = 5）
2. 切割长度为1的一段钢条，对剩下的求最优解r4 ，所以这种情况收益为r5 = p1 + r4 (i = 1)
3. 切割长度为2的一段钢条，对剩下的求最优解r3 ，所以这种情况收益为r5 = p2 + r3 (i = 2)
4. 切割长度为3的一段钢条，对剩下的求最优解r2 ，所以这种情况收益为r5 = p3 + r2 (i = 3)
5. 切割长度为4的一段钢条，对剩下的求最优解r1，所以这种情况收益为r5 = p4 + r1 (i = 4)
6. 最后，比较所有情况的收益大小，取最大收益r5=max(所有情况)
7. 方法里只需要调用一次递归

钢条切割问题–自顶而下递归方法

internal class Program
{
    static void Main(string[] args)
    {
        //int n = 11; //我们要切割售卖的钢条长度
        int[] p = { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };//索引代表钢条长度，值代表价格

        Console.WriteLine(UpDown(0,p));
        Console.WriteLine(UpDown(1,p));
        Console.WriteLine(UpDown(2,p));
        Console.WriteLine(UpDown(3,p));
        Console.WriteLine(UpDown(4,p));
        Console.WriteLine(UpDown(5,p));
        Console.WriteLine(UpDown(6,p));
        Console.ReadKey();

    }

    public static int UpDown(int n, int[] p) //求长度为n的最大收益
    {
        if(n == 0) return 0;  
        int tempMaxPrice = 0;
         for(int i = 1;i < n+1;i++)
        {
            int  maxPrice = p[i] + UpDown(n-i, p);
            if(maxPrice > tempMaxPrice)
            {
                tempMaxPrice = maxPrice;
            }
        }
         return tempMaxPrice;

    }
}

动态规划的方法求解

上面的方法之所以效率很低，是因为它反复求解相同的子问题。因此，动态规划算法安排求解的顺序，对每个子问题只求解一次，并将结果保存下来。如果随后再次需要此子问题的解，只需查找保存的结果，不重新计算。因此动态规划的方法是付出额外的内存空间来节省计算时间。

1. 带备忘录的自顶向下法

此方法依然是按照自然的递归形式编写过程，但过程中会保存每个子问题的解（通常保存在一个数组中）。当需要计算一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；如果没有保存过此解，按照正常方式计算这个子问题。我们称这个递归过程是带备忘的。

internal class Program
{
    static void Main(string[] args)
    {
        int n = 6; //我们要切割售卖的钢条长度

        //存储长度为x的最大收益是多少
        int[]  result = new int[n + 1];

        int[] p = { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };//索引代表钢条长度，值代表价格

        Console.WriteLine(UpDown(0, p, result));
        Console.WriteLine(UpDown(1, p, result));
        Console.WriteLine(UpDown(2, p, result));
        Console.WriteLine(UpDown(3, p, result));
        Console.WriteLine(UpDown(4, p, result));
        Console.WriteLine(UpDown(5, p, result));
        Console.WriteLine(UpDown(6, p, result));
        Console.ReadKey();

    }

    //自顶向下，带备忘录的求长度为n的最大收益
    public static int UpDown(int n, int[] p, int[] result) 
    {
        if (n == 0) return 0;
        if (result[n] != 0)
        {
            return result[n];
        }

        int tempMaxPrice = 0;
        for (int i = 1; i < n + 1; i++)
        {
            int maxPrice = p[i] + UpDown(n - i, p, result);
            if (maxPrice > tempMaxPrice)
            {
                tempMaxPrice = maxPrice;
            }
        }

        //保存存储长度为x的最大收益是多少
        result[n] = tempMaxPrice;

        return tempMaxPrice;

    }
}

2. 自底向上法

首先恰当的定义子问题的规模，是的任何问题的求解都只依赖于更小的子问题的解。因而我们将子问题按照规模排序，按从小到大的顺序求解。当求解某个问题的时候，它所依赖的更小的子问题都已经求解完毕，结果已经保存。

internal class Program
{
    static void Main(string[] args)
    {
        int[] result = new int[11];

        int[] p = { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };//索引代表钢条长度，值代表价格

        Console.WriteLine(BottomUp(0, p, result));
        Console.WriteLine(BottomUp(1, p, result));
        Console.WriteLine(BottomUp(2, p, result));
        Console.WriteLine(BottomUp(3, p, result));
        Console.WriteLine(BottomUp(4, p, result));
        Console.WriteLine(BottomUp(5, p, result));
        Console.WriteLine(BottomUp(6, p, result));
        Console.WriteLine(BottomUp(7, p, result));
        Console.WriteLine(BottomUp(8, p, result));
    }


    public static int BottomUp(int n, int[] p, int[] result)
    {

        for(int i = 1; i < n + 1; i++)
        {
            //下面取得 钢条长度为i的时候的最大收益
            int tempMaxPrice = -1;
            for(int j = 1; j <= i; j++)
            {
                int maxPrice = p[j] + result[i - j];
                if (maxPrice > tempMaxPrice)
                {
                    tempMaxPrice = maxPrice;
                }
            }
            //存储最优解
            result[i] = tempMaxPrice;
           
        }
        return result[n];
    }
}