算法导论 15.1 钢条切割

浏览数：22 / 时间：2015年06月08日

这里对这个DP问题做了代码实现，分为递归算法（自顶向下）和非递归算法（自下向上），以及拓展的自下向上算法的实现。

递归算法:

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 int size = 10;
 6 
 7 inline int max(int a, int b)
 8 {
 9     return a > b ? a : b;
10 }
11 
12 int CutRod(int p[], int n)
13 {
14     if (n == 0)
15         return 0;
16     else
17     {
18         int q = INT_MIN;
19         for (int i = 1; i < n; i++)
20         {
21             q = max(q, p[i] + CutRod(p, n - i -1));
22         }
23         return q;
24     }
25 }
26 
27 
28 
29 int main()
30 {
31     int a[] = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };
32     cout << CutRod(a, 6) << endl;
33 }

非递归算法：

#include<iostream>

using namespace std;

int size = 10;

inline int max(int a, int b)
{
    return a > b ? a : b;
}

int NonRecursionCutRod(int p[], int n)
{
    int *r = new int[n];
    r[0] = p[0];
    for (int j = 1; j < n; j++)
    {
        int q = p[j];
        for (int i = 0; i < j; i++)
        {
            if (q<(p[i] + r[j - i - 1]))
            {
                q = p[i] + r[j - i - 1];
            }
        }
        r[j] = q;
    }
    return r[n-1];
}

int main()
{
    int a[] = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };
    cout << NonRecursionCutRod(a, 6) << endl;
}

拓展非递归算法：

这里我建立了一个Result Struct用来作为返回结果，其实这个的意图：假如我们要求长度为j的解决方案，那么我们就在数组下标为j的单元中存上切割的第一段的长度，假如为i，那么剩下的部分可以通过去寻找j-i的方案，这样递归下去就可以得到长度为j的解决方案了。

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 typedef struct Result
 6 {
 7     int Max;
 8     int *Price;
 9 }Result;
10 
11 Result ExtendNonRecursionCutRod(int a[], int n)
12 {
13     Result result;
14     result.Price = new int[n+1];
15     int *r = new int[n+1];
16     r[1] = a[1];
17     result.Price[1] = a[1];
18     for (int j = 1; j <= n; j++)
19     {
20         int q = a[j];
21         int t = j;
22         for (int i = 1; i < j; i++)
23         {
24             if (q < (a[i] + r[j - i]))
25             {
26                 q = a[i] + r[j - i];
27                 t = i;
28             }
29         }
30         r[j] = q;
31         result.Price[j] = t;
32     }
33     result.Max = r[n];
34     return result;
35 }
36 
37 int main()
38 {
39     int a[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };
40     Result  result = ExtendNonRecursionCutRod(a, 10);
41     cout << result.Max << endl;
42     for (int i = 1; i < 10; i++)
43         cout << result.Price[i] << "    ";
44 }