《算法导论》学习（十七）----动态规划之钢条切割（C语言）-Toy模板网

这篇具有很好参考价值的文章主要介绍了《算法导论》学习（十七）----动态规划之钢条切割（C语言）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

本文主要讲解了钢条切割问题的解决方案，并且给出了C语言代码。其中涉及到了动态规划的思想，会在之后的文章中详细讲解

一、钢条切割问题

1.问题背景

Serling公司购买长钢条，将其切割成短钢条进行出售。切割工序本身没有成本支出。管理层希望得到最优的切割方法。
现在我们知道Serling公司出售一段长度为 $i$ 英寸的钢条的价格为 $p_i(i=1,2,3,...,n)$ ，单位为美元。钢条的长度都为整英寸。

举例一个价格的样表如下：


长度 $i$	1	2	3	4	5	6	7	8	9	10
价格 $p_i$	1	5	8	9	10	17	18	20	24	30

2.问题描述

现在我们的问题是：

给定一段长度为 $n 英寸$ 的钢条和一个价格表 $p_i(i=1,2,...,n)$ ，求切割钢条的方案，使得收益 $q$ 最大化。

3.问题的难点

（1）情况较多

首先我们有如下结论：
$长度为n英寸的钢条共有2^{n-1}种不同的切割方案$
具体的分析如下：

对于长度为n英寸的钢条，我们有n-1个可切割点
那么每个切割点的情况分为两种：切断或者不切断
有n-1个点，每个点有两种情况

综上所述：总情况为 $2^{n-1}$

（2）消除重复子问题

我们可以试想以下，当我们想知道长度为7的钢条如何切割，会需要先解决一部分子问题，记为集合A。
而我们要解决长度为5英寸的钢条的子问题集为B
那么A与B肯定存在公共的子问题需要求解

那么这样看来，解决长度越长，包含更多的重复的子问题来浪费资源。

二、问题解决方案

1.问题的特点

（1）最优化子结构

首先该问题是求解一个最优化的问题。

其次我们可以将该最优化问题分解为诸多最优化的子问题来求解
举个例子
对于长度为4的问题，我们可以这样分割：
$4 的最优解 = 最优（ 1 的价格 + 3 的最优， 2 价格 + 2 的最优， 3 的价格 + 1 的最优 < 1 的最优也便是 1 的价格 > ）$
可以发现该最优问题确实可以分解为诸多最优子问题来解决。
涉及到了子问题，这样我们就顺其自然地用递归等方法来解决问题。

（2）重复子问题

这里前文已经分析过。会有资源耗费在解决重复的子问题上。
那么我们需要想方案让这些子问题仅解决一次，这里就用到了动态规划的思想。
我们有两种具体的方案：

带备忘的自顶向下
自底向上

下文将进行具体讲解

2.最优化解决方案

（1）自顶向下的普通递归

该方案就是编程实现上文中将问题分解为子问题的过程。
采用递归的方式，遍历所有的情况。
最后时间复杂度将是可怕的 $O(2^n)$

（2）带备忘的自顶向下

该方案对比普通的自顶向上的方案仅有一个改进之处
就是采用一个存储数组存储已经解决的子问题，如果下次遇到已经解决过的子问题，那么直接在存储数组中查找即可，节省了时间

（3）自底向上

该方案是先从最底层的子问题开始解决，接着向上一层解决高一层的子问题。
以此不断循环，最后将总体问题解决。

3.构建最优解的结构

我们现在得到了最大利润，但是如何得到最优的方案呢？
我们需要引入一个存储数组s，存储“切割的第一刀”

现在我们来理解什么是“切割的第一刀”，回想以下我们如何将长度4的问题进行切割的：
$4 的最优解 = 最优（ 1 的价格 + 3 的最优， 2 价格 + 2 的最优， 3 的价格 + 1 的最优 < 1 的最优也便是 1 的价格 > ）$
对于上述的例子来说，可能的“切割的第一刀”有：1，2，3。
我们可以理解为，切割这个第一刀后，问题被分解为最优子问题。
因此我们需要存储所有问题的”第一刀“，然后就可以通过一个简单的循环找到具体的切割方案。

三、C语言代码

1.三种方案的函数代码

（1）自顶向下的普通递归

//返回最大值函数
int MAX(int a,int b)
{
	if(a>=b)
	{
		return a;
	}
	else
	{
		return b;
	}
} 
//自顶向下不加备忘机制
int CUT_ROD(int *p,int n,int size)
{
	int q=0;
	int i=0;
	if(n==0)
	{
		return 0;
	}
	q=-10;
	if(n>=size)
	{
		for(i=1;i<size;i++)
		{
			q=MAX(q,p[i]+CUT_ROD(p,n-i,size));
		}	
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			q=MAX(q,p[i]+CUT_ROD(p,n-i,size));
		}
	}
	return q;
}

（2）带备忘的自顶向下

//返回最大值函数
int MAX(int a,int b)
{
	if(a>=b)
	{
		return a;
	}
	else
	{
		return b;
	}
} 
//自顶向下加备忘机制方法
int MEMORIZED_CUT_ROD_DO(int *p,int n,int *w,int *s,int size)
{
	int q=0;
	int i=0;
	if(w[n]>=0)
	{
		return w[n];
	}
	q=-10;
	if(n>=size)
	{
		for(i=1;i<size;i++)
		{
			if(q<(p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size)))
			{
				s[n]=i;
				q=p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size);
			}			
		}
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			if(q<(p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size)))
			{
				s[n]=i;
				q=p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size);
			}			
		}		
	}
	w[n]=q;
	return q;
}
int MEMORIZED_CUT_ROD(int *p,int n,int *w,int *s,int size)
{
	int i=0;
	for(i=0;i<=n;i++)
	{
		w[i]=-1;
	}
	w[0]=0;
	s[0]=0;
	return MEMORIZED_CUT_ROD_DO(p,n,w,s,size);
}

（3）自底向上

//返回最大值函数
int MAX(int a,int b)
{
	if(a>=b)
	{
		return a;
	}
	else
	{
		return b;
	}
} 
//自底向上的方法
int BOTTOM_UP_CUT_ROD(int *p,int n,int *w,int *s,int size)
{
	int q=0;
	w[0]=0;
	s[0]=0;
	int j=0;
	int i=0;
	for(j=1;j<=n;j++)
	{
		q=-10;
		if(j>=size)
		{
			for(i=1;i<size;i++)
			{
				if(q<(p[i]+w[j-i]))
				{
					s[j]=i;
					q=p[i]+w[j-i];
				}
			}			
		}
		else
		{
			for(i=1;i<=j;i++)
			{
				if(q<(p[i]+w[j-i]))
				{
					s[j]=i;
					q=p[i]+w[j-i];
				}
			}			
		}
		w[j]=q;
	}
	return w[n];
}

2.整体测试代码

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


 
//由于要存放长度为0时，钢条的价格为0 
//因此市场上可以出售钢条长度为1~SIZE-1
//这SIZE-1种整数长度
//比如SIZE=5时
//钢条可以切成1，2，3，4 
#define SIZE 6//输入规模 

//钢条长度每增加一单位 
//其价格增加LIM+1
//因此它是钢条价格的单位随机增量 
#define LIM 7//随机数的范围：0~(LIM-1)

//钢条的总长度 
#define Length 10; 



//返回最大值函数
int MAX(int a,int b)
{
	if(a>=b)
	{
		return a;
	}
	else
	{
		return b;
	}
} 



//自顶向下不加备忘机制
int CUT_ROD(int *p,int n,int size)
{
	int q=0;
	int i=0;
	if(n==0)
	{
		return 0;
	}
	q=-10;
	if(n>=size)
	{
		for(i=1;i<size;i++)
		{
			q=MAX(q,p[i]+CUT_ROD(p,n-i,size));
		}	
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			q=MAX(q,p[i]+CUT_ROD(p,n-i,size));
		}
	}
	return q;
} 



//自顶向下加备忘机制方法
int MEMORIZED_CUT_ROD_DO(int *p,int n,int *w,int *s,int size)
{
	int q=0;
	int i=0;
	if(w[n]>=0)
	{
		return w[n];
	}
	q=-10;
	if(n>=size)
	{
		for(i=1;i<size;i++)
		{
			if(q<(p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size)))
			{
				s[n]=i;
				q=p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size);
			}			
		}
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			if(q<(p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size)))
			{
				s[n]=i;
				q=p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size);
			}			
		}		
	}
	w[n]=q;
	return q;
}
int MEMORIZED_CUT_ROD(int *p,int n,int *w,int *s,int size)
{
	int i=0;
	for(i=0;i<=n;i++)
	{
		w[i]=-1;
	}
	w[0]=0;
	s[0]=0;
	return MEMORIZED_CUT_ROD_DO(p,n,w,s,size);
}




//自底向上的方法
int BOTTOM_UP_CUT_ROD(int *p,int n,int *w,int *s,int size)
{
	int q=0;
	w[0]=0;
	s[0]=0;
	int j=0;
	int i=0;
	for(j=1;j<=n;j++)
	{
		q=-10;
		if(j>=size)
		{
			for(i=1;i<size;i++)
			{
				if(q<(p[i]+w[j-i]))
				{
					s[j]=i;
					q=p[i]+w[j-i];
				}
			}			
		}
		else
		{
			for(i=1;i<=j;i++)
			{
				if(q<(p[i]+w[j-i]))
				{
					s[j]=i;
					q=p[i]+w[j-i];
				}
			}			
		}
		w[j]=q;
	}
	return w[n];
}



//打印钢条的最优组合
void print_max(int *s,int n)
{
	int i=n-1;
	printf("价格最优情况下，钢条的长度组合之一如下：\n"); 
	while(i>0)
	{
		printf("%5d",s[i]);
		i=i-s[i];
	}
	printf("\n");
} 



//主函数
int main()
{
	int i=0;
	int maxp=0;
	int n=Length; 
	int p[SIZE];
	int w[n+1];
	int s[n+1];
	srand((unsigned)time(NULL));
	int temp=0;
	for(i=0;i<SIZE;i++)
	{
		p[i]=temp;
		temp=temp+rand()%LIM+1;
	}
	for(i=0;i<SIZE;i++)
	{
		printf("%5d",p[i]);
	}
	printf("\n");
	//自顶向下不加备忘机制
	maxp=CUT_ROD(p,n,SIZE);
	printf("max profit is %5d\n",maxp);
	//自顶向下加备忘机制方法
	maxp=MEMORIZED_CUT_ROD(p,n,w,s,SIZE);
	printf("max profit is %5d\n",maxp);
	print_max(s,n+1);
	//自底向上的方法
	maxp=BOTTOM_UP_CUT_ROD(p,n,w,s,SIZE);
	printf("max profit is %5d\n",maxp);
	for(i=0;i<=n;i++)
	{
		printf("%5d",w[i]);
	}
	printf("\n");
	print_max(s,n+1);
	return 0;
}