长度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); } } ~~~ 测试结果：