算法导论之动态规划：钢条切割

冷不防 2022-07-24 06:20 186阅读 0赞

**问题描述**：

给定一段长度为n英寸的钢条和一个价格表Pi(i=1,2,……,n)，求切割钢条方案，使得销售收益rn最大。

我们如果采用自顶向下的**递归实现**的话：

#define max(x,y) x>y?x:y
    CUT_ROD(double p[],int n){
    	if(n==0){
    		return 0;
    	}
    	int q = INT_MIN;
    	int i=1;
    	for(;i<=n;i++){
    		q=max(q,p[i]+CUT_ROD(p,n-1));
    	}
    }

那么这样的时间复杂度就是O(2^n)。

所以我们需要另寻他法，即动态规划的方法。

第一种、**自底向上法**。

这种方法需要恰当的定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。

因此我们可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个子问题时，它所依赖的那些小问题都已经求解完毕。

每个子问题只需运行一次，当我们求解它的时，它的所有前提子问题都已求解完毕。

代码实现如下：

#include <stdio.h>
    #define max(x,y) x>y?x:y
    
    int doBottomUpCutRod(int *value,int n,int valueLength){
    	int maxValue[n+1];
    	maxValue[0]=0;
    	int i,j,TempMax=0;
    	for(i=0;i<n;i++){
    		TempMax=0;
    		for(j=0;j<=i && j<valueLength;j++){
    			TempMax = max(TempMax,value[j]+maxValue[i-j]);
    		}
    		maxValue[i+1]=TempMax;
    	}
    	return maxValue[n];
    }
    
    int main(int argc, char *argv[])
    {
    	int value[10]={1,5,8,9,10,17,17,20,24,30};
    	srand((unsigned) time(NULL));
    	int n = rand()%11;
    	printf("length is %d and result of value is:%d\n",n,doBottomUpCutRod(value,n,sizeof(value)/sizeof(int)));
    	return 0;
    }

第二种、 **带备忘录的自顶向下法**。

自己实现吧！！！哈哈

第三种、**自底向上法的扩展**。

对长度为j的钢条不仅计算最大收益，还保存最优解对应的第一段钢条的切割长度。

实现如下：

#include <stdio.h>
    #define max(x,y) x>y?x:y
    
    int *record,*maxValue;
    int doBottomUpCutRod(int *value,int n,int valueLength){
    	record = (int *)malloc(sizeof(int)*(n+1));
    	maxValue = (int *)malloc(sizeof(int)*(n+1));
    	maxValue[0]=0;
    	int i,j,TempMax=0;
    	for(i=0;i<n;i++){
    		TempMax=0;
    		for(j=0;j<=i && j<valueLength;j++){
    			if(TempMax<value[j]+maxValue[i-j]){
    				TempMax = value[j]+maxValue[i-j];
    				record[i+1]=j+1;
    			}
    		}
    		maxValue[i+1]=TempMax;
    	}
    	return maxValue[n];
    }
    
    int main(int argc, char *argv[])
    {
    	int value[10]={1,5,8,9,10,17,17,20,24,30};
    	srand((unsigned) time(NULL));
    	int n = rand()%11;
    	printf("length is %d and result is:%d\n",n,doBottomUpCutRod(value,n,sizeof(value)/sizeof(int)));
    	int i;
    	printf("this is maxValue:\n");
    	for(i=0;i<=n;i++)
    		printf("%d\t",maxValue[i]);
    	printf("\nthis is record:\n\t");
    	for(i=1;i<=n;i++)
    		printf("%d\t",record[i]);
    	return 0;
    }

这些动态规划算法的时间复杂度是O(n^2)。

**参考资料**：  
算法导论  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51422309  
作者：WSYW126