程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 算法導論--動態規劃(鋼條切割)

算法導論--動態規劃(鋼條切割)

編輯:C++入門知識

算法導論--動態規劃(鋼條切割)


鋼條切割問題

現有一段長度為n英寸的鋼條和一個價格表pi,求切割方案使銷售利益最大rn最大
這裡寫圖片描述

長度為n英寸的鋼條共有2n?1種不同的切割方案,因為可以每個整英寸的位置都可以決定切割或者不切割。

為了得到rn最大,可以把這個問題分成子問題求解,先切一刀,再考慮余下的部分的最大收益即求
rn=max{pk+rn?k}(k=1,2,3…n-1),
pk部分不進行繼續切割,直接作為一個整體售出 ;
rn?k部分繼續切割,考慮所有的情況,分成子問題。
求出所有k值對應的收益最大者作為rn<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPtKy09C/ycTcsru9+NDQyM66zsfQuO7A+9Lm1+6087y0PG5vYnI+cm49cG48L25vYnI+PC9wPg0KPHA+PHN0cm9uZz7X28nPPC9zdHJvbmc+o7ogPG5vYnI+cm49bWF4KHBpK3JuP2kpPC9ub2JyPiAoaT0xLDIsMyZoZWxsaXA7biAsIDxub2JyPnIwPTA8L25vYnI+KTwvcD4NCjxoMSBpZD0="動態規劃求解">動態規劃求解

考慮上面的算法實現:rn=max(pi+rn?i) (i=1,2,3…n , r0=0),為了計算出rn必須計算出所有情況的切割方法,即有n個分支,第i個分支又對應著i個子分支,所以若采用遞歸調用計算所有情況,調用次數將是2n次。運行時間為n的指數函數。

上面的分析知,其中重復計算了很多次子問題,如果有個好的計算順序,子問題先計算一次,把結果保存下來,下次再遇到這個子問題,只需要查表即可。動態規劃方法是付出額外的內存空間來節省計算時間。

帶備忘的自頂向下法

仍采用遞歸的方法,但過程中保存已求解過子問題的解,當需要一個子問題的解時,首先檢查是否已經保存過此解。

int Memoized_Cut_Rod(int *p,int n)
{   
    int i=0;
    int * r = (int *)malloc((n+1)*sizeof(int));  //分配空間,用來存儲已經計算過的子問題
    for (i=0;i<=n;i++)                          //初始化
        r[i] = -1;
    return Memoized_Cut_Rod_Aux(p,n,r);         
}
int Memoized_Cut_Rod_Aux(int *p,int n,int *r)
{
    int q= -1,i;
    if (r[n] >=0)   //首先檢查是否已經計算過,若有,直接返回
        return r[n];
    if (n == 0)     //鋼條長度為0,收益為0
        q=0;
    else
    {
        q = -1;
        for (i=1;i<=n;i++) 
        {
           q=Max(q,p[i]+Memoized_Cut_Rod_Aux(p,n-i,r));   //自頂向下遞歸
        }
        r[n] = q;        //保存子問題的值
    }

    return q;        //返回最大的收益
}

自底向上法

把子問題按規模排序,按由小到大的順序進行求解,當求解某個問題時,它所依賴的子問題已經被計算過,結果已經保存,這樣每個子問題只需要計算一次。

int Bottom_Up_Cut_Rod(int *p,int n)
{
int * r = (int *)malloc((n+1)*sizeof(int));   //分配空間,用來存儲已經計算過的子問題
int i,j,q=-1;
  r[0]=0;
  for (j=1;j<=n;j++)
    {
       q=-1;
       for(i=1;i<=j;i++)
       {
           q=Max(q,p[i]+r[j-i]);   //自底向上,由小到大求解子問題
       }
       r[j]=q;   //保存求解後的結果
    }
  return r[n];
}

重構解

上面的代碼是返回的最大收益,並沒有返回具體切割方法。下面代碼保存了每種尺寸,對應的左邊部分大小(即作為整體售出部分)

int Extended_Bottom_Up_Cut_Rod(int *p,int n)
{
    int * r = (int *)malloc((n+1)*sizeof(int));   
    int i,j,q=-1;
    s = (int *)malloc((n+1)*sizeof(int));  //保存每次切割前左邊部分剩余尺寸
    s[0]=0;
    r[0]=0;
    for (j=1;j<=n;j++)
    {
        q=-1;
        for(i=1;i<=j;i++)
        {

            if (p[i]+r[j-i] > q)
            {
                s[j] = i;      //保存左邊部分(作為整體售出的部分)
                q = p[i] + r[j-i];
            }
        }
        r[j]=q;
    }

    return r[n];
}

輸入鋼條的具體切割方法:

void Print_Cut_Rod_Solution(int *p,int n)
{
    while(n>0)
    {
        printf("%d   ",s[n]);   //循環輸出尺寸為n的鋼條切割方法
        n=n-s[n];
    }
}

例程

/************************************************************************
CSDN 勿在浮沙築高台 
http://blog.csdn.net/luoshixian099
算法導論--動態規劃(鋼條切割)
2015年6月2日                    
************************************************************************/
#include 
#include 
int *s=NULL;
int Memoized_Cut_Rod_Aux(int *p,int n,int *r);
int Max(int a,int b)
{
    return a>b?a:b;
}
int Memoized_Cut_Rod(int *p,int n)
{   
    int i=0;
    int * r = (int *)malloc((n+1)*sizeof(int));  //分配空間,用來存儲已經計算過的子問題
    for (i=0;i<=n;i++)                          //初始化
        r[i] = -1;
    return Memoized_Cut_Rod_Aux(p,n,r);         
}
int Memoized_Cut_Rod_Aux(int *p,int n,int *r)
{
    int q= -1,i;
    if (r[n] >=0)   //首先檢查是否已經計算過,若有,直接返回
        return r[n];
    if (n == 0)     //鋼條長度為0,收益為0
        q=0;
    else
    {
        q = -1;
        for (i=1;i<=n;i++)
        {
           q=Max(q,p[i]+Memoized_Cut_Rod_Aux(p,n-i,r));
        }
        r[n] = q;        //保存子問題的值
    }

    return q;        //返回最大的收益
}
int Bottom_Up_Cut_Rod(int *p,int n)
{
int * r = (int *)malloc((n+1)*sizeof(int));   //分配空間,用來存儲已經計算過的子問題
int i,j,q=-1;
  r[0]=0;
  for (j=1;j<=n;j++)
    {
       q=-1;
       for(i=1;i<=j;i++)
       {
           q=Max(q,p[i]+r[j-i]);   //自底向上,由小到大求解子問題
       }
       r[j]=q;   //保存求解後的結果
    }
  return r[n];
}

int Extended_Bottom_Up_Cut_Rod(int *p,int n)
{
    int * r = (int *)malloc((n+1)*sizeof(int));   
    int i,j,q=-1;
    s = (int *)malloc((n+1)*sizeof(int));  //保存每次切割前左邊部分剩余尺寸
    s[0]=0;
    r[0]=0;
    for (j=1;j<=n;j++)
    {
        q=-1;
        for(i=1;i<=j;i++)
        {

            if (p[i]+r[j-i] > q)
            {
                s[j] = i;      //保存左邊部分(作為整體售出的部分)
                q = p[i] + r[j-i];
            }
        }
        r[j]=q;
    }

    return r[n];
}
void Print_Cut_Rod_Solution(int *p,int n)
{

    while(n>0)
    {
        printf("%d   ",s[n]);   //循環輸出尺寸為n的鋼條切割方法
        n=n-s[n];
    }
}
void main()
{
   int p[]={0,1,5,8,9,10,17,17,20,24,30};
   int i;
   for (i=1;i<=10;i++)
   {
     //printf("%d\n",Memoized_Cut_Rod(p,i));
     printf("尺寸為%d的最大收益:%d ",i,Extended_Bottom_Up_Cut_Rod(p,i));
    // printf("%d  \n",s[i]);
     printf("切割方法:");
     Print_Cut_Rod_Solution(p,i);
     free(s);
     s=NULL;
     printf("\n");
   }
}

這裡寫圖片描述

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved