【动态规划----钢条切割问题】

介绍

在算法导论中的第15章,经典的动态规划样题:钢条切割问题,相较于在文中给出的伪代码,本文中的代码,更完善地解决了切割问题.文中的代码不仅针对两段的切割问题,考虑了可能出现2段切割事件,还解决了当钢条长度超出最大单价长度的情况,给出的动态规划公式为:
dp[i]=max{p[i],dp[i-1]+dp[1],dp[i-2]+dp[2]…dp[i-i/2]+dp[i/2]} i<=n i为切割钢条长度,n为钢条的单位价格数目
dp[i]=max{dp[i-1]+dp[1],dp[i-2]+dp[2]…dp[i-i/2]+dp[i/2]} i>n

代码

#include <iostream>
#include<vector>
//#include<string>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */


//p:1-10的价格    n:切割条的长度 
vector<int> max_gangtiao(vector<int> p,int n)
{
	vector<int> dp(n+1);
	for(int i=0;i<=n;i++)
	{
		if(i<=10)//当切割的长度小于10时,需要和价格p中的价格进行对比,大于长度10时,只需找到最大的组合即可 
		{
			dp[i]=p[i];	
		}
	
		for(int j=0;j<=i/2;j++)
		{
			dp[i]=max(dp[i],dp[i-j]+dp[j]);
		}
	}
	return dp;
}


int main(int argc, char *argv[]) {
	
	vector<int> p={0,1,5,8,9,10,17,17,20,24,30};//价格表 
	int n=20;//钢条长度 
	vector<int> result=max_gangtiao(p,n);
	for(int i=0;i<=n;i++) 
		cout<<result[i]<<endl;
	//若是需要钢条的切割方法,可以使用组合的方式,尝试找出,对应长度的最有组合,即钢条的每个单独的切割长度 
	
	return 0;
}