动态规划与钢条切割问题 C++实现

动态规划与钢条切割问题 C++实现

一、原理

我们可以用拉格朗日乘数法，求解给定条件下的方程最优解，同样，动态规划算法也是用于在一定条件下的求解最优解的方法。

它和分治方法很相似，都是通过组合子问题来求解原问题。一般适用于动态规划算法的问题具备两个条件：最优子结构和重叠子问题。

考虑一般的递归算法，总是会重复调用问题的子结构，来解决原问题，可是正是因为重复调用时间与空间开销会很大。有没有什么办法能将递归方法变的简单一点呢？这就是动态规划中的带备忘自顶向下法所要解决的问题。

反过来考虑既然要解决的问题中有很多子结构，能否找到最小的一个子结构，然后下一步要求解的子结构依赖于这个最小的子结构，下一步要求解的子结构又依赖于刚才求解的子结构，以此类推，直到原问题的求解。这就是动态规划中自底向上法所要解决的问题。

现在来详细说说这两种方法：
第一种方法叫带备忘的自顶向下法（top-down with memoization）。这种方法通过自然的递归形式编写，但过程会保存每个子问题的解（通常会保存在一个向量或者三列表中）。当需要一个子问题的解时，过程首先会检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则，按照通常的方式计算这个子问题。
也可以这么说，自顶向下法类似于深度优先搜索。

第二种方法称为自底向上方法（bottom-up method）。这种方法一般需要且当定义子问题“规模”的概念，是的任何子问题的求解都只依赖于“更小的”自问题的求解。因而我们可以将子问题按规模排序，按由小到大的顺序进行求解。当求某个子问题时，它所依赖的哪些更小的子问题都已经求解完毕，结果已经保存。每个子问题斗智求解一次，当我们求解它时，它的所有前提子问题都以求解完成。
也可以这么说，自底向上方法类似于拓扑排序。

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

那么如何用动态规划算法求解问题呢？需要按照如下四个步骤：
1、刻画一个最优解的结构特征。
2、递归地定义最优解的值。
3、计算最优解的值，通常采用自底向上法。
4、利用计算出的信息构造一个最优解。
步骤1~3是动态规划算法求解问题的基础，如果需要第4步，那么就需要在第3步中增加一些额外的信息。

下面通过一个实例来展示如何使用动态规划算法。

二、示例

一个著名的例子就是钢条切割问题，说给定一个钢条长度和对应的价格 pi ，对一长度为 n 的钢条，如何切割使其收入最大。

设每段钢条的收入为 ri ，那么对于 rn(n≥1) 我们可以用最优切割收入来描述它：

rn=max(pn,r1+rn−1,r2+rn−2,…,rn−1+r1)

可以简化为：

rn=max1≤i≤n(pi+rn−i)

那么其递归实现为：

//Recursion.
int Cut_Rod_Recursion(const vector<int> &temp_Vec, const size_t &temp_n) {
    if (temp_n == 0) {
        return 0;
    }

    auto temp_q = INT_MIN;

    for (auto i = 1; i <= temp_n; ++i) {
        temp_q = max(temp_q, temp_Vec[i] + Cut_Rod_Recursion(temp_Vec, temp_n - i));
    }

    return temp_q;
}

令 T(n) 为第二个参数值为 n 时。Cut_Rod_Recursion的调用次数。可以证明 T(n)=2n 。

那么有了递归的定义，我们就可以使用动态规划算法来求解了，先将递归改为带“备忘”机制的：

//Top-down with memoization of part 1.
int Memoized_Cut_Rod_Aux(const vector<int> &temp_Vec, const size_t &temp_n, vector<int> &temp_VecR) {
    auto temp_q = INT_MIN;

    if (temp_VecR[temp_n] >= 0) {
        return temp_VecR[temp_n];
    }

    if (temp_n != 0) {
        for (auto i = 1; i <= temp_n; ++i) {
            temp_q = max(temp_q, temp_Vec[i] + Memoized_Cut_Rod_Aux(temp_Vec, temp_n - i, temp_VecR));
        }
    }
    else {
        temp_q = 0;
    }

    temp_VecR[temp_n] = temp_q;

    return temp_q;
}

//Top-down with memoization of part 2.
int Memoized_Cut_Rod(const vector<int> &temp_Vec, const size_t &temp_n) {
    vector<int> temp_VecR;
    temp_VecR.resize(temp_n + 1);

    for (auto &i : temp_VecR) {
        i = INT_MIN;
    }

    return Memoized_Cut_Rod_Aux(temp_Vec, temp_n, temp_VecR); 

}

可以看到在递归的基础上我们增加了一个 temp_VecR 向量来保存子结构所计算的值。第6~8行就是用来返回这个值。

同样我们也可以使用自底向上的方法解决此问题：

//Bottom-up method.
int Boyyom_Up_Cut_Rod(const vector<int> &temp_Vec, const size_t &temp_n) {
    vector<int> temp_VecR;
    temp_VecR.resize(temp_n + 1);
    temp_VecR[0] = 0;

    for (auto j = 1; j <= temp_n; ++j) {
        auto temp_q = INT_MIN;

        for (auto i = 1; i <= j; ++i) {
            temp_q = max(temp_q, temp_Vec[i] + temp_VecR[j - i]);
        }

        temp_VecR[j] = temp_q;
    }

    return temp_VecR[temp_n];
}

这两个算法的运行时间均为 Θ(n2) 。显然要比递归版更省时省力。

以上三个算法走知识输出了最优解，但并没有输出具体的最优解，所以需要对算法增加额外的信息来输出，这就是之前所说的第4步：

//Extended version of bottom-up method.
void Extended_Bottom_Up_Cut_Rod(const vector<int> &temp_Vec, const size_t &temp_n) {
    vector<int> temp_VecR, temp_VecS;
    temp_VecR.resize(temp_n + 1);
    temp_VecS.resize(temp_n + 1);
    temp_VecR[0] = 0;

    for (auto j = 1; j <= temp_n; ++j) {
        auto temp_q = INT_MIN;

        for (auto i = 1; i <= j; ++i) {
            if (temp_q < temp_Vec[i] + temp_VecR[j - i]) {
                temp_q = temp_Vec[i] + temp_VecR[j - i];
                temp_VecS[j] = i;
            }
        }

        temp_VecR[j] = temp_q;
    }

    cout << temp_VecR[temp_n] << " ";

    auto n = temp_n;
    while (n > 0) {
        cout << temp_VecS[n];
        n -= temp_VecS[n];
    }
}

关于最优子结构与重叠子问题

有了之前的一些描述，应该对动态规划有了一定的了解，那么什么样的问题才满足最优子结构与重叠子问题呢？

思考这样一个问题：都给定一个有向图 G=(V,E) 和两个顶点 u,v∈V 。问题一为：求解其无权最短路径。问题二为：求解其无权最长路径。

显然问题一是有最优子结构的，我们将 u,v 之间在 w 处划分成两条单独的子线路，如果 u→w 与 w→v 为最短路径显然其加起来 u→v 也为最短路径，我们可以使用这种方法递归地定义求解方法，再通过动态规划就能求出两点之间的最短路径。然而对于问题二，无法找到其最优的子结构，因为可以有环路。问题二其实也是 NP 完全问题。

显然对于第一题，求解过程中所有子问题都不会重复。二对于问题二因为有环路所以路径上肯定有重复的顶点出现。之前所列出的钢铁切割问题也是一样，左右的子问题都是独立存在，也就是所有子问题都具有无关性。

对于重叠的子问题，如果递归算法反复求解相同的子问题，那么我们就称最优化问题有重叠子问题。

问题无关性即是存在最优子结构，这和重叠子问题，看上去似乎是矛盾的存在，然而，他们所描述的是两个不同的概念。两个子问题如果不共享资源，他们就是独立的，而重叠是指两个子问题实际上是同一个问题，知识作为不同子问题出现而已。

完整示例代码

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> Price{ 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };

//Recursion.
int Cut_Rod_Recursion(const vector<int> &temp_Vec, const size_t &temp_n) {
    if (temp_n == 0) {
        return 0;
    }

    auto temp_q = INT_MIN;

    for (auto i = 1; i <= temp_n; ++i) {
        temp_q = max(temp_q, temp_Vec[i] + Cut_Rod_Recursion(temp_Vec, temp_n - i));
    }

    return temp_q;
}

//Top-down with memoization of part 1.
int Memoized_Cut_Rod_Aux(const vector<int> &temp_Vec, const size_t &temp_n, vector<int> &temp_VecR) {
    auto temp_q = INT_MIN;

    if (temp_VecR[temp_n] >= 0) {
        return temp_VecR[temp_n];
    }

    if (temp_n != 0) {
        for (auto i = 1; i <= temp_n; ++i) {
            temp_q = max(temp_q, temp_Vec[i] + Memoized_Cut_Rod_Aux(temp_Vec, temp_n - i, temp_VecR));
        }
    }
    else {
        temp_q = 0;
    }

    temp_VecR[temp_n] = temp_q;

    return temp_q;
}

//Top-down with memoization of part 2.
int Memoized_Cut_Rod(const vector<int> &temp_Vec, const size_t &temp_n) {
    vector<int> temp_VecR;
    temp_VecR.resize(temp_n + 1);

    for (auto &i : temp_VecR) {
        i = INT_MIN;
    }

    return Memoized_Cut_Rod_Aux(temp_Vec, temp_n, temp_VecR); 

}

//Bottom-up method.
int Boyyom_Up_Cut_Rod(const vector<int> &temp_Vec, const size_t &temp_n) {
    vector<int> temp_VecR;
    temp_VecR.resize(temp_n + 1);
    temp_VecR[0] = 0;

    for (auto j = 1; j <= temp_n; ++j) {
        auto temp_q = INT_MIN;

        for (auto i = 1; i <= j; ++i) {
            temp_q = max(temp_q, temp_Vec[i] + temp_VecR[j - i]);
        }

        temp_VecR[j] = temp_q;
    }

    return temp_VecR[temp_n];
}

//Extended version of bottom-up method.
void Extended_Bottom_Up_Cut_Rod(const vector<int> &temp_Vec, const size_t &temp_n) {
    vector<int> temp_VecR, temp_VecS;
    temp_VecR.resize(temp_n + 1);
    temp_VecS.resize(temp_n + 1);
    temp_VecR[0] = 0;

    for (auto j = 1; j <= temp_n; ++j) {
        auto temp_q = INT_MIN;

        for (auto i = 1; i <= j; ++i) {
            if (temp_q < temp_Vec[i] + temp_VecR[j - i]) {
                temp_q = temp_Vec[i] + temp_VecR[j - i];
                temp_VecS[j] = i;
            }
        }

        temp_VecR[j] = temp_q;
    }

    cout << temp_VecR[temp_n] << " ";

    auto n = temp_n;
    while (n > 0) {
        cout << temp_VecS[n];
        n -= temp_VecS[n];
    }
}

int main() {
    auto temp_n = 6;

    cout << Cut_Rod_Recursion(Price, temp_n) << endl;
    cout << Memoized_Cut_Rod(Price, temp_n) << endl;
    cout << Boyyom_Up_Cut_Rod(Price, temp_n) << endl;
    Extended_Bottom_Up_Cut_Rod(Price, temp_n);

    return 0;
}