动态规划 - 钢条切割

动态规划

动态规划方法通常用来求解最优化问题，这类问题可以有很多可行解，每个解都有值，我们希望寻找具有最优值（最小值或最大值）的解。我们称这样的解为问题的一个最优解决，而不是最优解，因为可能有多个解都达到最优值

动态规划与分治法

动态规划与分治方法相似，都是通过组合子问题的解来求原问题。

分治法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题的重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子问题）。

在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题，而动态规划算法对每个子问题值求解一次，将其保存在一个表格中，从而无需每次求解子问题时重新计算，避免了这种不必要的计算工作

动态规划的设计步骤

• 1、刻画一个最优解的结构特征
• 2、递归定义最优解的值
• 3、计算最优解的值，通常采用自底向上的方法
• 4、利用计算出的信息构造一个最优解

步骤1-3是动态规划求解问题的基础，如果我们仅仅是求解最优解的值，而非解本身，可以忽略步骤4。如果确实要做步骤4，有时需要在执行步骤3的过程中维护一些额外的信息，以便来构造一个最优解

钢条切割

给定一段长度为n英寸的钢条和一个价格表p_i(i=1，2，...，n)，求解切割钢条方案，使得销售收益r_n最大。注意，如果长度为n英寸的钢条价格p_n足够大，最优解可能就是完全不需要切割。

分析

假定我们知道出售一段长度为i英寸的钢条价格为p_i(i=1，2，...，n)，钢条长度为整英寸，如下

162025012825029.png

考虑n=4的情况，我们所有可能的切割方案如下

下载.jpeg

由上图可知，将一段长度为4英寸的钢条切割为两段各长为2英寸的钢条，将产生p₂+p₂=5+5=10的收益，为最优解。

不难发现规律，对于长度为n英寸的钢条共有2^n-1种不同的分割方案，因为在距离钢条左端i（i=1，2，...，n-1）英寸处，我们总可以选择切割或者不切割。

我们用普通的加法符号表示切割方案，因此7=2+2+3表示将长度为7英寸的钢条切割为三段——两段长度为2英寸、一段长度为3英寸。如果一个最优解将钢条切割为k段（对某个1kn），那么最优切割方案：n = i₁ + i₂ + ... + i_k。将钢条切割为长度分别为i₁ 、i₂ 、 ... 、 i_k小段，得到的最大收益为r_n = p_i1 + p_i2 + ... + p_ik

对于上述价格表，我们可以先观察所有最优收益值r_i(i=1，2，...，10)及对应的最优切割方案：

• r₁=1，切割方案：1 = 1（无切割）
• r₂=5，切割方案：2 = 2（无切割）
• r₃=8，切割方案：3 = 3（无切割）
• r₄=10，切割方案：4 = 2 + 2
• r₅=13，切割方案：5 = 2 + 3
• r₆=17，切割方案：6 = 6（无切割）
• r₇=18，切割方案：7 = 1 + 6 或 7 = 2 + 2 + 3
• r₈=22，切割方案：8 = 2 + 6
• r₉=25，切割方案：9 = 3 + 6
• r₁₀=30，切割方案：10 = 10（无切割）

更一般地，对于r_n（n1）,可以用更短地钢条的最优收割收益来描述它：r_n = max(p_n，r₁ + r_n-1 ，r₂ + r_n-2，...，r_n-1 + r₁)

• p_n对应不切割，直接出售长度为n英寸的钢条方案
• 其他n-1个参数对应另外n-1种切割方案：对每个i=1，2，...，n-1，首先将钢条切割长度为i和n-i的两段，接着求解这两段的最优收益r_i和r_n-i（每种方案的最优收益为两段的最优收益之和）

由于无法预知哪种方案会获得最优收益，需要考虑所有可能的i，选出其中收益最大者。

除了上述方案，钢条切割问题还存在一种相似的但更为简单的递归求解方案：

我们将钢条从左边切割长度为i的一段，只对右边剩下的长度为n-i的一段继续进行切割（递归求解），对左边的一段则不再进行切割。即问题分解为：将长度为n的钢条分解为左边开始一段，以及对剩余部分继续分解的结果。

这样，不做任何切割的方案可以描述为：第一段的长度为n，收益为p_n，剩余部分长度为0，对应收益为r₀=0。所以上面公式可以得到简化版本：r_n = max(p_i + r_n-i)

自顶向下递归

/**
 @param p 收益
 @param n 钢条长度
 @return 最大收益
 */
int CutSteel(const int *p, int n)
{
    if (n == 0)
        return 0;

    int q = -1;
    for (int i = 1; i <= n; i++) {
        q = max(q, p[i] + CutSteel(p, n-i));
    }
    return q;
}

int main(int argc, const char * argv[]) {
    int prices[] = {0,1,5,8,9,10,17,17,20,24,30};
    for (int i = 1; i <= 10; i++) {
        printf("尺寸为%d的最大收益为：%d\n", i, CutSteel(prices, i));
    }
    return 0;
}

运行输出

尺寸为1的最大收益为：1
尺寸为2的最大收益为：5
尺寸为3的最大收益为：8
尺寸为4的最大收益为：10
尺寸为5的最大收益为：13
尺寸为6的最大收益为：17
尺寸为7的最大收益为：18
尺寸为8的最大收益为：22
尺寸为9的最大收益为：25
尺寸为10的最大收益为：30
Program ended with exit code: 0

动态规划方法

上面的递归方法效率很低，因它反复方法求解相同的子问题。而动态规划对每个子问题只求解一次，并将结果保存下来，如果随后再次需要此子问题，只需查找保存的结果，而不必重新计算，这是典型的时空权衡，但是时间上的节省是巨大的。

动态规划有两种等价的实现方法

• 带备忘录的自顶向下方法

此方法仍然按照自然的递归形式编写过程，但过程种会保存每个子问题的解（通常保存在一个数组或散列表中）。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是则直接返回保存的值，从而节省计算时间，否则，按通常方式计算这个子问题。

• 自底向上方法

这种方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小”子问题的求解。因而我们可以将子问题按规模排序，按由小到大的顺序进行求解。当求某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只求解一次，当求解它时，它的所有前提子问题都已求解完成。

两种方法得到的算法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自底向上方法的时间复杂性函数通常具有更小的系数

带备忘录的自顶向下

int MemorizedCutSteelCore(const int *p, int n, int *r)
{
    if (r[n] > 0) //检查值是否存在
        return r[n];

    int q = -1;
    if (n == 0) //钢条长度为0，收益为0
    {
        q = 0;
    }
    else
    {
        for (int i = 1; i <= n; i++) {
            int temp = p[i] + MemorizedCutSteelCore(p, n - i, r); //自顶向下递归
            q =  max(q,temp);
        }
    }
    r[n] = q; //保存子问题的值
    return q;
}

int MemorizedCutSteel(const int *p , int n)
{
    int *r = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        r[i] = -1;
    }
    return MemorizedCutSteelCore(p, n, r);
}

自底向上

int BottomUpCutSteel(const int *p, int n)
{
    int *r = new int[n+1];
    r[0] = 0;

    for (int i = 1; i <= n; i ++) {
        int q = -1;
        for (int j = 1;j <= i; j++) {
            int temp = p[j] + r[i - j];
            // q = q > temp? q : temp;
            q = max(q, temp);
        }
        r[i] = q;
    }
    return r[n];
}

自顶向下与自底向上算法具有相同的渐进运行时间，都为O(n²)

重构解

上面的动态规划返回最优解的值，但并未返回解本身（一个长度列表，给出切割后每段钢条的长度）。所以可以扩展动态规划算法，使之对每个子问题不仅保存最优收益值，还保存对应的切割方案。

 void ExtendedBottomUpCutSteel(const int *p, int n, int *r, int *s)
{
    r[0] = 0;
    for (int i = 1; i <= n; i++) {
        int q = -1;
        for (int j = 1; j <= i; j++) {
            int temp = p[j-1] + r[i-j];
            if (temp > q) {
                q = temp;
                s[i] = j;
            }
        }
        r[i] = q;
    }
}

// r[]保存长度为i的钢条最大收益,s[]保存最优解对应的第一段钢条的切割长度
void PrintCutSteel(const int *p, int n, int *r, int *s)
{
    ExtendedBottomUpCutSteel(p, n, r, s);
    cout << "长度为" << n << "的钢条最大收益为:" << r[n] << endl;
    cout << "最优方案的钢条长度分别为：";
    while (n>0) {
        cout << s[n] << " ";
        n = n - s[n];
    }
    cout << endl;
}

int main(int argc, const char * argv[]) {
    int n;
    cout << "输入钢条的尺寸：" << endl;
    while (cin >> n) {
        int *p = new int[n];
        for (int i = 0; i < n; i++) {
            cin >> p[i];
        }
        int *r = new int[n + 1];
        int *s = new int[n + 1];

        PrintCutSteel(p, n, r, s);
    }
    return 0;
}

运行程序

输入钢条的尺寸：
7
1 5 8 9 10 17 17 
长度为7的钢条最大收益为:18
最优方案的钢条长度分别为：1 6 

参考

《算法导论》