钢条的最优切割问题_a题 钢板最优切割路径问题

问题描述：

一家公司购买长钢条，将其切割成短钢条出售，假设切割本身没有成本，长度为i的短钢条的价格为Pi。那给定一段长度为n的钢条和一个价格表Pi，求钢条的切割方案使得收益Rn最大。

举一个例子来说：

例如某公司以单价26元买到了一批长度为10的钢条，目前各长度钢条的市场价如下表所示：

要求：

随机生成钢条长度n和不同长度钢条的价格信息，编写程序确定一种钢条的切割方案，使公司的收益最大化。

动态规划：
对于长度为n的钢条，我们可以先切一刀，切下长度为1-10的钢条，共10种切法，
最大收益就是切下的钢条收益和剩下钢条的最大收益之和。

钢条长度为1的最大收益计算出来，保存到r[1]

长度为2的钢条，遍历每一种切法，收益最大的保存到r[2]

计算长度为n的钢条的最大收益，此时r数组已经保存了1——n-1长度钢条的最大收益
遍历这10种切法，就可以找到最大的收益

由于每种钢条长度的最大收益都被保存在数组r中，避免了很多的重复计算

设计思路：

对于一个动态规划问题：

第一步先确定最优解的结构。如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。

第二步定义最优解的计算公式

第三步根据得到的求最优解公式，计算出结果。

第四步构造出最优解。

算法设计：

首先生成随机价格，将不同长度的钢条价格生成，然后通过算法去计算最优解，即最优切割问题的最优解，得到最高价格。

代码：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int N[11]={};//存储价格 
int r[11]={};
int upToDown(int);
int maxx(int a,int b);
int main()
{	
	int z,x,c,a[11]={0};
	printf("钢条长度:"); 
	for(z=0;z<=10;z++)
	printf("%3d",z);
	//随机数生成，生成不同钢条长度的不同价格 
	
	srand((unsigned)time(NULL));
	for(z=0;z<=10;z++)
	{
		a[z]=rand()%(25)+4;
	}
	printf("\n");
	for(z=0;z<=9;z++)
		for(x=z+1;x<=10;x++)
		{
			if(a[z]>a[x])
			{
				c=a[z];
				a[z]=a[x];
				a[x]=c;
			}
		}
		a[0]=0;
		a[1]=1,a[2]=4,a[3]=7;
		printf("钢条价格:");
	for(z=0;z<=10;z++)
		N[z]=a[z];
		
		for(z=0;z<=10;z++)
			printf("%3d",a[z]);
		
	//对钢条进行切割计算				
	int current;
	puts("\n输入你要裁剪的钢条长度：");
	scanf("%d",&current);
	int i;
	printf("%d长的钢条最大收益是：%d\n",current,upToDown(current));
	printf("各个长度的收益情况：\n长度：");
	for(i=0;i<=current;i++)
	{
		printf("%3d ",i);
	}
	printf("\n");
	printf("收益：");
	for(i=0;i<=current;i++)
	{
		printf("%3d ",r[i]);
	}
} 
int upToDown(int n) //每次返回的值是当前长度n的最大收益 
{
	
		
	if(n==0)
		return 0;
 
	int q=N[n];	
	int i;
	for(i=1;i<n;i++)
		q=maxx(q,r[i]+upToDown(n-i));
	r[n]=q;
	if(r[n]!=0)
		return r[n];
	return q;
}
int maxx(int a,int b)//比较大小 
{
	if(a>=b)
		return a;
	else
		return b;
}

算法求解：