長度i ? ?? 1 ? 2 ?3 ?4?5??? 6 ??? 7??8??? 9?10 價格Pi?? 1 ? 5 ? 8?9? 10? 17 ??17? 20? 24? 30 上圖分別是長度為i的鋼條的價格；那么現在一根長度為n的鋼條，求如何切割，使得利潤最大？ 《算法導論》205頁。 如果只求最大利潤的值，不需要知道分割過程，有以下兩種方法： ~~~ #include "test.h" #define MAXLEN 11 //****算法導論，動態規劃，鋼條分割，P205 //自底向上，僅記錄最優解結果 int ButtomUpCutRod(int priceList[], int n) { int highest[MAXLEN] = {-1}; //記錄每個長度對應的最優解 highest[0] = 0; //長度為0的最優解（最大利潤）為0 int j = 0; for (j = 1; j <= n; j++) { int highest_j = -1; //長度為j的最優解 int i; for (i = 1; i <= j; i++) //長度為i的最優解為不切割時，或者為切割長度為i的利潤加上長度為j-i的最優解 highest_j = max(highest_j, priceList[i] + highest[j - i]); highest[j] = highest_j; //記錄長度為j的最優解值 } return highest[n]; } /**********方法二************/ //該函數計算長度為n的鋼條的最大利潤 int MemorizedCutRod_aux(int priceList[], int n, int highest[]) { int highest_n = -1; if (highest[n] >= 0) //如果長度為n的最優解已經被記錄了，就直接返回 return highest[n]; if (n == 0) //長度為0的鋼條利潤為0 highest_n = 0; else { //還未記錄鋼條的利潤，則計算之 int i; for (i = 1; i <= n; i++) //長度為n的鋼條最大利潤為不切割，或者為切割長度i的利潤加上長蘇為n-i的最大利潤 highest_n = max(highest_n, priceList[i] + MemorizedCutRod_aux(priceList, n-i, highest)); } highest[n] = highest_n; //記錄長度為n的最大利潤 return highest_n; } //自頂向下，僅記錄最優解結果 int MemorizedCutRod(int priceList[], int n) { int highest[11]; int i; //初始化最大利潤列表 for (i = 0; i < MAXLEN; i++) highest[i] = -1; return MemorizedCutRod_aux(priceList, n, highest); } ~~~ 如果不僅要求得最大利潤，還要知道如何切割，方法和上面方法很類似，只是需要記錄下切割第一段的長度： ~~~ pair<vector<int>, vector<int> > ButtomUpCutRodSolution(vector<int> &priceList, int n) { vector<int> highest; //每個元素依次記錄長度遞增的鋼條最優解結果 vector<int> solution(priceList.size()); //記錄長度為n的鋼條的解決方案 int highest_j = -1; highest.push_back(0); //長度為0的鋼條最優解為0 int j; for (j = 1; j <= n; j++) { //依次求長度為1直到長度為n的鋼條的最優解 highest_j = -1; int i; for (i = 1; i <= j; i++) { //長度為j的鋼條最優解的計算 if (highest_j < priceList[i] + highest[j - i]) { highest_j = priceList[i] + highest[j - i]; solution[j] = i; //記錄切割中取得最優解的切割長度 } } highest.push_back(highest_j); //記錄長度為j的鋼條的最優解 } return make_pair(highest, solution); } //該算法不僅輸出最優解，而且給出最優解的一個切割方案 void printSolution(vector<int> &priceList, int n) { pair<vector<int>, vector<int> > ivec = ButtomUpCutRodSolution(priceList, n); cout << "highest price3: " << ivec.first.at(n); //輸出最優解 vector<int> solu = ivec.second; cout << " solution: "; while (n > 0) { //輸出解決方案 cout << solu[n] << " "; n -= solu[n]; } cout << endl; vector<int>::iterator iter = solu.begin(); while (iter != solu.end()) cout << *(iter++) << " "; cout << endl; cout << endl << endl; } //對以上方法的測試： int main() { int priceList[] = {0,1, 5, 8, 9,10,17,17,20,24,30}; vector<int> priceVec(priceList, priceList + sizeof(priceList) / sizeof(int)); int n; while (1) { cout << "input length: "; cin >> n; cout << "highest price: " << ButtomUpCutRod(priceList, n); cout << " highest price2: " << MemorizedCutRod(priceList, n) << endl; printSolution(priceVec, n); } } ~~~ 測試結果：