[dynamic planning - steel bar cutting]

Introduce

In the introduction to algorithms, chapter 15 Chapter , Classic dynamic programming sample questions : Steel cutting problem , Compared with the pseudo code given in the article , The code in this article , It solves the cutting problem more perfectly . The code in this article is not only for the cutting of two paragraphs , Consider possible 2 Segment cutting event , It also solves the problem when the length of steel bar exceeds the maximum unit price , The dynamic programming formula given is :
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 Is the length of cutting steel bar ,n Is the unit price of steel bar
dp[i]=max{dp[i-1]+dp[1],dp[i-2]+dp[2]…dp[i-i/2]+dp[i/2]} i>n

Code

#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 The price of     n: Length of cutting strip  
vector<int> max_gangtiao(vector<int> p,int n)
{
	vector<int> dp(n+1);
	for(int i=0;i<=n;i++)
	{
		if(i<=10)// When the cutting length is less than 10 when , Need and price p Compare the prices in , Greater than length 10 when , Just find the largest combination  
		{
			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};// price list  
	int n=20;// Steel bar length  
	vector<int> result=max_gangtiao(p,n);
	for(int i=0;i<=n;i++) 
		cout<<result[i]<<endl;
	// If you need the cutting method of steel bar , You can use combinations , Try to find out , The most significant combination of corresponding lengths , That is, each individual cutting length of the steel bar  
	
	return 0;
}