动态规划算法

钢条切割问题

自顶向下递归实现

#include 
using namespace std;
 
int CUT_ROD(int p[], int n)
{
    if (n == 0)
        return 0;
    int q = -10000;
    for (int i = 0; i < n; i++)
        q = max(q, p[i] + CUT_ROD(p, n - 1 - i));
    return q;
}
 
int main()
{
 
    int a[10] = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    cout << CUT_ROD(a, 10) << endl;
    system("pause");
    return 0;
}

带备忘的自顶向下

#include 
using namespace std;
 
const int N = 10005;
int r[N];
int Memorized_cut_rod_aux(int p[], int n)
{
 
    int q = -10000;
    if (r[n] >= 0)
        return r[n];
    else if (n <= 0)
        return 0;
 
    for (int i = 1; i <= n; i++)
        q = max(q, p[i - 1] + Memorized_cut_rod_aux(p, n - i));
 
    // r[n] = q;
    return r[n] = q;
}
 
int main()
{
    for (int i = 0; i < N; i++)
        r[i] = -1;
    int a[10] = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    cout << Memorized_cut_rod_aux(a, 9) << endl;
    system("pause");
    return 0;
}

自底向上

#include
using namespace std;
 
const int N = 10005;
int r[N];
int Bottom_up_cut_rod(int p[], int n)
{
    r[0] = 0;
 
    for (int j = 1; j <= n; j++)
    {
        int q = -10000;
        for (int i = 1; i <= j; i++)
        {
            q = max(q, p[i - 1] + r[j - i]);
        }
        r[j] = q;
    }
    return r[n];
}
 
int main()
{
    for (int i = 0; i < N; i++)
        r[i] = -1;
    int a[10] = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    cout << Bottom_up_cut_rod(a, 10) << endl;
    system("pause");
    return 0;
}

---

未完待续

参考资料：

算法导论 第3版

Cutting a Rod | C++ Implementation | Dp Explanation | PrepInsta