[算法]DP解决钢条切割问题

Mon, 01 Jun 2015 16:05:00 +0800

DP解决钢条切割问题

（原题见算法导论·动态规划）

对长度为n的钢条进行切割，对应的切割长度和价格对应如下：

int cost[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

比如1对应价值1,10对应价值30。即相应的下标和值的对应。现求切割所得最大效益mx。

递归算法

    int cut_rod(int *cost,int n)
    {
        if(n == 0) return 0;
        int limit = MIN(n,10);       //分割第一条的上限
        int mx =  -1;
        for(int i = 1;i <= limit; ++i)
            mx = maxnum(mx,cost[i]+cut_rod(cost,n-i));    //取当前值于递归值的最大值
        return mx;
    }

由于对相同子问题的重复求解，T(n) = 2^n

递归标记数组算法（自顶而下）（DFS）

    int mem_cut_rod(int *cost,int n,int *mem)   //mem数组长度为n,所有元素须在其他函数中初始化为-1
    {
        int mx;
        if (mem[n] >= 0) return mem[n];     //对于求过的问题，直接返回存储的值
        if (n == 0) mx = 0;
        else mx = -1;
        int limit = MIN(n,10);
        for(int i = 1;i <= limit; ++i)
            mx = maxnum(mx,cost[i]+mem_cut_rod(cost,n-i,mem));   //后面的内容和递归型是一样的
        mem[n] = mx;    //储存计算出的新值
        return mx;  
    }

逆拓扑序DP（自底向上）


    int bottom_cut_rod(int *cost,int n)
    {
        int mem[MEM_LEN+1];                              //MEM_LEN = n，设置标记数组
        mem[0] = 0;                                       //i,j将从1开始，这里收益是0
        for(int i = 1; i <= n; ++i)                              //从第一个问题开始求解
        {
            int mx = -1;
            int limit = MIN(i,10);
            for(int j = 1;j <= limit; ++j)
                mx = maxnum(mx,cost[j] + mem[i-j]);     //求解最小的问题
            mem[i] = mx;
        }
        return mem[n];
    }

我们可以看到，2,3 的解法复杂度均为O(n^2)。

动态规划 on 子恒的博客

[算法]DP解决钢条切割问题

DP解决钢条切割问题

递归算法

递归标记数组算法（自顶而下）（DFS）

逆拓扑序DP（自底向上）