| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 1056 人关注过本帖
标题:算法导论读书笔记之钢条切割问题
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
  已结贴   问题点数:3  回复次数:1   
算法导论读书笔记之钢条切割问题
算法导论读书笔记之钢条切割问题
巧若拙(欢迎转载,但请注明出处:http://blog.
给定一段长度为n英寸的钢条和一个价格表 pi (i=1,2, …,n),求切割钢条的方案,使得销售收益rn最大。注意,如果长度为n英寸的钢条价格pn足够大,最优解可能就是完全不需要切割。
若钢条的长度为i,则钢条的价格为Pi,如何对给定长度的钢条进行切割能得到最大收益?
长度i    1    2    3   4     5      6      7     8      9      10
价格Pi   1    5    8   9    10     17    17    20    14     30
 
i = 1时,钢条不可切割,r[1]= 1;
i = 2时,钢条可分割为1+ 1,其价格为2。若不分割(0 + 2),价格为5。即r[2] = 5;
i = 3时,钢条可分割为0+ 3,1 + 2。r[3] = 8;
同理可得:
r[4] = 10(2+ 2);
r[5] = 13(2+ 3);
r[6] = 17(0+ 6);
r[7] = 18(1+ 6或4+ 3=> 2 + 2 + 3);
.......
我们可以发现,长度为7时,将其切割为长度4与长度3的钢条,并对两个钢条分别求最优解:长度4的最优解为r[4] = 10(2 + 2),长度3的最优解为r[3] = 8,即可得r[7] =r[4]+ r[3] =>原问题的最优解等于子问题的最优解之和的最大值
     我们将钢条左边切割下长度为 i 的一段,只对右边剩下的长度为 n-i 的一段继续进行切割(递归求解),对左边的一段不再进行切割。即问题分解的方式为:将长度为n 的钢条分解为左边开始一段,以及剩余部分继续分解的结果。这样,不做任何切割的方案就可以描述为:第一段的长度为n ,收益为 pn,剩余部分长度为0,对应的收益为r0=0。于是公式的简化版本:
 
因此,在计算r[i]时,所求值即为r[0] +r[i],r[1]+ r[i- 1],r[2]+ r[i- 2],...  ,r[i- 1] +r[1] 之间的最大值,而在动态规划中,r[0]——r[i - 1]的值在计算r[i]之前已经保存好了,进行少量的运算便能取得最优结果。

使用动态规划算法求解最优钢条切割问题有两种等价的实现方法。
第一种方法称为带备忘的自顶向下法。此方法按照递归方式编写过程,但过程会保存每个子问题的解——用数组r[i]记录总长度为i的钢管的最大收益值。当需要一个子问题的解时,过程首先检查是否已经保存过此解,如果是,直接返回保存的值,否则递归计算这个子问题。
    第二种方法称为自底向上法,这是动态规划的常用方法,这种方法需要我们将子问题按照规模排序,按由小到大的顺序进行求解——在本题中即按i从1到n的顺序求解。每个子问题只需求解一次,并及时把结果记录下来,以便后面调用。
两种方法得到的算法具有相同的渐进运行时间,仅有的差异是在某些特殊情况下,自顶向下方法并未真正递归的考察所有可能的子问题。由于没有频繁的递归函数调用的开销,自底向上方法的时间复杂性函数通常具有更小的系数。
代码如下:
#include<stdio.h>
#include<stdlib.h>

#define MAX 20001   //最大长度
#define INFINITY -999999   //负无穷大

void PrintCutRodSolution(int p[], int n);//自底向上法
void BottomUpCutRod(int p[], int r[], int s[], int n);//记录总长度为i的钢管的最大收益值r[i]及其第一段钢条的切割长度s[i]
void MemoizedCutRod(int p[], int n);//带备忘的自顶向下法
int MemoizedCutRodAux(int p[], int r[], int s[], int n);//递归计算r[i]的值

int main()
{
    int p[MAX] = {0};
    int i, n = 50;
   
    for (i=1; i<=n; i++)//随机获取长度价格,但确保长的比短的价值高
    {
        do{
            p[i] = (i>4)? (p[i-4] + rand()%20+1) : rand()%20+1;
        }while (p[i] <= p[i-1]);
        printf("%7d", p[i]);
    }
   
    printf("\n");
    PrintCutRodSolution(p, n);//自底向上法
    printf("\n");
    MemoizedCutRod(p, n);//带备忘的自顶向下法

    return 0;
}

void PrintCutRodSolution(int p[], int n)//自底向上法
{
    int r[MAX] = {0};//r[i]记录总长度为i的钢管的最大收益值  
    int s[MAX] = {0};//s[i]记录r[i]对应的第一段钢条的切割长度
    int i;
   
    BottomUpCutRod(p, r, s, n);
//    printf("最大价值:\n");
//    for (i=1; i<=n; i++)
//    {
//        printf("%2d:%3d  ", r[i], s[i]);
//    }
//    printf("\n");
   
    printf("最大价值: %d\n", r[n]);
    printf("切割方案:\n");
    while (n > 0)
    {
        printf("%d\t", s[n]);
        n -= s[n];
    }
    printf("\n");
}

void BottomUpCutRod(int p[], int r[], int s[], int n)//记录总长度为i的钢管的最大收益值r[i]及其第一段钢条的切割长度s[i]
{
    int i, j, max;
   
    r[0] = 0;
    for (i=1; i<=n; i++)//钢管总长度为i
    {
        max = INFINITY;
        for (j=1; j<=i; j++)
        {
            if (max < p[j] + r[i-j])//如果分解成长度j和长度i-j两部分能获得更大收益,则更新最大收益值max,并记录对应的第一段钢条的切割长度s[i]
            {
                max = p[j] + r[i-j];
                s[i] = j;
            }
        }
        r[i] = max; //记录总长度为i的钢管的最大收益值
    }
}

void MemoizedCutRod(int p[], int n)//带备忘的自顶向下法
{
    int r[MAX] = {0};//r[i]记录总长度为i的钢管的最大收益值  
    int s[MAX] = {0};//s[i]记录r[i]对应的第一段钢条的切割长度
    int i;
   
    for (i=0; i<=n; i++)//初始化
        r[i] = INFINITY;
   
    printf("最大价值: %d\n", MemoizedCutRodAux(p, r, s, n));
    printf("切割方案:\n");
    while (n > 0)
    {
        printf("%d\t", s[n]);
        n -= s[n];
    }
    printf("\n");
}

int MemoizedCutRodAux(int p[], int r[], int s[], int n)//递归计算r[i]的值,并同时记录s[i]的值
{
    int i, max, temp;
   
    if (r[n] >= 0)//已经记录过了就不再重复计算
        return r[n];
    if (n == 0)
        max = 0;
    else
    {
        max = INFINITY;
        for (i=1; i<=n; i++)
        {
            temp = p[i] + MemoizedCutRodAux(p, r, s, n-i);//计算把钢条分为长度为i和n-i两部分所得到的最大收益值
            if (temp > max)//更新最大收益值并记录对应s[i]的值  
            {
                max = temp;
                s[n] = i;
            }
        }
    }

    return r[n] = max;
}
搜索更多相关主题的帖子: 读书笔记 价格表 切割 如何 收益 
2014-12-12 21:38
wp231957
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:神界
等 级:版主
威 望:398
帖 子:13398
专家分:51686
注 册:2012-10-18
  得分:3 
楼主辛苦

DO IT YOURSELF !
2014-12-19 10:41
快速回复:算法导论读书笔记之钢条切割问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.094775 second(s), 7 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved