動态規劃解決鋼條切割問題

題目描述

一家公司購買長鋼條，将其切割成短鋼條出售，切割本身沒有成本，長度為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;


}