動态規劃：鋼條切割問題

            動态規劃與分治法相似，都是通過組合子問題的解來求解原問題。回顧下分治法的原理：它将問題劃分為互不相交的子問題（注意：互不相交），遞歸求解子問題，再将它們的解組合起來，即為原問題的解。

       但是，動态規劃與分治法不同，有以下幾點：

1）對于子問題重疊的情況，分治法則重複求解，不高效。而動态規劃對每個子問題隻求解一次，因為它将子問題的解進行儲存，當遇到重複的子問題時，不再計算，隻需查找替代即可；

2）動态規劃對原問題的劃分存在n種子問題劃分的可能性，它需要從n種劃分中選擇最優解，故動态規劃常被用于求解最優化問題；

             接下來，通過鋼條切割的案例展示動态規劃的運用。

1、鋼條切割

        鋼條切割問題的描述：給定一段長度為n英寸的鋼條和一個價格表，求鋼條切割的方案，使得銷售收益最大化。

             鋼條的長度和價格

   length : 1  2  3  4  5  6   7   8   9   10

   price  :  1  5  8  9 10 17 17 20 24 30

問題的分解方式：将長度為n的鋼條切割分解為左邊開始一段i，以及對右邊剩餘長度為n-i的鋼條繼續切割（遞歸求解），對左邊的一段不再進行切割。于是，最大切割收益可以描述為：                    接下來通過n=4的鋼條切割問題的子問題圖來說明重疊子問題。

上圖，n=4時的鋼條切割子問題圖。頂點的标号給出了子問題的規模。有向邊（x，y）表示求解x時需要子問題y的解。舉例：n=4時，它包含子問題n=3,2,1,0；n=3時，它包含子問題n=2,1,0。是以重疊的子問題即為n=2,1,0，故當求解了n=3的子問題，對于n=4時的其他子問題，如n=2,1,0不需要再次求解，隻需要查找替代即可。

2、鋼條切割問題的僞代碼

      先來看自頂向下實作的切割。 MEMOIZED_CUT_ROD(p,n)

let r[0..n] be a new array

for i=0 to n 

r[i]=-1

return Memorized_cut_rod_Aux(p,n,r);

Memorized_cut_rod_Aux(p,n,r)

if r[n]>=0

return r[n]

if n==0

q=0

else 

    q=-1

for i=1 to n

q=max(q,p[i]+Memorized_cut_rod_Aux(p,n-i,r))

r[n]=q

return q

         本文對自頂向下的切割用C進行實作，但是這裡提及切割的另一個版本自底向上，下面是其僞代碼。 BOTTOM-UP-CUT-ROD(p,n)

let r[0..n]be a new array

r[0]=0

for j=1 to n

q=-1

for i=1 to j

q=max(q,p[i]+r[j-i])

r[j]=q

return r[n]

3、自頂向下算法實作

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int max(int x,int y)
{
	return x>y ? x:y;
}
int Memorized_cut_rod_Aux(int p[], int n, int r[])
{
	int q;
	int i;
	if (r[n]>=0)//prohibit over-calculate same question
	{
		return r[n];
	}

	if (n==0)
	{
		q=0;
	}
	else
	{

		q=-1;
		for (i=1; i<=n; i++)
		{

			q=max(q,p[i]+Memorized_cut_rod_Aux(p,n-i,r));
		}
	}
	r[n]=q;
	return q;
}


int Memorized_cut_rod(int p[], int n)
{
	int i;
	int *r;
	r=(int*)malloc(sizeof(int)*n);
	for (i=0; i<n; i++)
	{
		r[i]=-1;
	}

	return Memorized_cut_rod_Aux(p,n,r);

}

void main()
{
//鋼條的長度和價格
// length : 1 2 3 4 5  6  7  8  9  10
// price  : 1 5 8 9 10 17 17 20 24 30

	int price[]={0,1,5,8,9};
	int n=4;
        printf("鋼條長度 is %d\n",n);
	int value=0;
	value=Memorized_cut_rod(price,n);
	printf("profit is most: %d\n",value);

}           

4、結果驗證

對n=4,本算法給出的收益是10，符合要求。對于其他長度，可自行驗證。