动态规划解决钢条切割问题

题目描述

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

输入要求

输入钢条的长度n。

输出要求

输出获得的最大收益。

输入样例

7

输出样例

18

具体思路：对n进行切割，保存切割产生的最大收益，如value[10]表示对10进行切割产生的最大收益，明显其中有4种切割方式，并且用到了前面产生的结果

value[10] = max{value[1]+value[9], value[2]+value[8], + ...........value[5]+value[5]}
           

从一开始的初始数据的第2个位置开始进行切割，当切割产生的价值大于当前价值的时候，则对最大价值进行更新，最终得到的第n个值就是我们想要的结果

具体实现的代码如下：

/*
	
	钢条切割问题

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

	输入钢条的长度n，输出得到最大收益

	对n进行切割，保存切割产生的最大收益，如value[10]表示对10进行切割产生的最大收益，明显其中有4种
	切割方式，并且用到了前面产生的结果

	value[10] = max{value[1]+value[9], value[2]+value[8], + ...........value[5]+value[5]}

*/

#include<iostream>

using namespace std;

//保存切割的结果
int value[1000] = { 0,1, 5, 8,9,10, 17, 17, 20, 24, 30 };

void main() {
	
	int i,j, n;

	cin >> n;

	//从长度为2开始切割
	for (i = 2; i <= n; i++) {

		//刚开始默认整条不进行切割
		int max_value = value[i];

		//从第一个开始向前进行切割，当到达中间一半的时候，就不用继续了，因为后面的和前面的重复了
		for (j = 1; j <= i / 2; j++) {

			//如果当前切割的大于当前最大值，则对当前的最大值进行更新
			if (value[j] + value[i - j] > max_value) {

				max_value = value[j] + value[i - j];

				

			}

			//更新value的值
			value[i] = max_value;

		}

	}

	cout << value[n] << endl;


}