动态规划：钢条切割问题

            动态规划与分治法相似，都是通过组合子问题的解来求解原问题。回顾下分治法的原理：它将问题划分为互不相交的子问题（注意：互不相交），递归求解子问题，再将它们的解组合起来，即为原问题的解。

       但是，动态规划与分治法不同，有以下几点：

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，符合要求。对于其他长度，可自行验证。