算法導論--動態規劃（鋼條切割）

鋼條切割問題

現有一段長度為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");
   }
}