目錄
一、題目大意
?二、大致思路
三、具體實現?
一、題目大意
? ? ? ?一家公司購買長鋼條，將其切割成短鋼條出售，切割本身沒有成本，長度為i的短鋼條的價格為Pi。那給定一段長度為n的鋼條和一個價格表Pi,求鋼條的切割方案使得收益Rn最大。提示：將鋼條切割為長度為i和n - i兩段，接著求解這兩段的最優切割收益Ri和Rn - i
?二、大致思路
? ? ? ?本題用到的知識點就是動態規劃，以下簡稱DP，我在解決此題的時候，思路在剛開始的時候是亂著的，首先是題目的意思不明確，后來發現，長度不同的鋼條的價格可以自行輸入（有點“長度為5的鋼條的最大價值是建立在4的基礎上”的感覺）即使是在有提示的情況下，我還是沒有思路。
? ? ? ?我大腦里將此題與其他DP類型的題目對比，準備用一個二維數組把所有的情況存儲一下，但是發現二維數組的橫縱坐標代表的屬性似乎找不全。后來豁然開朗，解決本題的核心思想就是：分成兩段！一根鋼條拿來時，他的最大價值將會在兩種情況產生：一刀也不切，就切一刀。到這里有的同學可能就不理解了。讓我慢慢道來，此處的切一刀其實是分出一個比例，我們把這個切一刀之后左右兩邊的比稱為“最大價值比”，這一刀左側切出來的最大價值加上右邊的最大價值，不就是整段鋼條的最大價值了嗎？有了這個思路之后，我寫出來了如下代碼。做完之后再返回頭思考，其實這個價格表就是一個入手點，我們可以根據此表，把每一個不同長度的鋼條的最大收益計算出來，例如我有了前10個1-10長度的鋼條的最大收益，那么長度為11的鋼條的最大收益就可以從（1，10）、（2，9）、（3，8）……..(5，6)來選出。這就是只切一刀的真實含義。做了幾組DP題目之后，自己也有了一點感覺，無非是遞推式，已經知道1，2，3，4時的最優解，求5，6，7，8……等時的最優解。
三、具體實現?
#include<stdlib.h>
#include<iostream>
#include<stdio.h>
using namespace std;
int value[1000] = { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };//按照題目給的數據初始化，之后用來記錄每個長度的最優值
int abcmp(int a, int b)//比較兩個int型數的大小，返回大的數
{int max = 0;max = a > b ? a : b;return max;
}
void result(int n)//用二重循環將每一個長度的鋼條的最大收益記錄
{int i, j;//循環變量for (i = 2; i <= n; i++)//只有2及以上單位長度才能分割，所以從2開始{int max = value[i];//剛開始的最大值默認是一段鋼條不切的情況for (j = 1; j <= i / 2; j++)//循環條件這樣的原因是，//一旦j過半，切割兩段的情況就重復了{max = abcmp(max, value[j] + value[i - j]);//比較當前最大值}value[i] = max;}
}
int main()
{int n = 0;//鋼條的長度cout << "請輸入鋼條的長度：";cin >> n;result(n);//調用函數cout << "收益的最大值為：" << value[n] << endl;system("pause");return 0;
}
)
