自頂向下遞歸實現(Recursive top-down implementation)
程序CUT-ROD對等式(14.2)進行了實現，偽代碼如下：
CUT-ROD(p, n)if n == 0return 0q = -∞for i = 1 to nq = max{q, p[i] + CUT-ROD(p, n - i)}return q
上面解決中重復對一個子結構問題重復求解了，我們可以把這個過程記錄下來
使用動態規劃求解最優鋼條切割(Using dynamic programming for optimal rod cutting)
MEMOIZED-CUT-ROD(p, n)let r[0 : n] be a new array // will remember solution values in rfor i = 0 to nr[i] = -∞return MEMOIZED-CUT-ROD-AUX(p, n, r)MEMOIZED-CUT-ROD-AUX(p, n, r)if r[n] ≥ 0 // already have a solution for length n ?return r[n]if n == 0q = 0else q = -∞for i = 1 to n // i is the position of the first cutq = max{q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r)}r[n] = q // remember the solution value for length nreturn q
代碼
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>class Solution {
public:Solution(int x):len(x){}int fun() {for (int i = 0; i <= len; i++) {memory[i] = 0; // 初始化}for (int i = 1; i <= len; i++){int q = min;for (int k = 1; k <= i; k++){q =std::max( q , price[k] + memory[i - k]); // 每次切割一次，這是核心record[i] = k;}memory[i] = q;}return memory[len];}private:int price[11] = {0,1,5,8,9,10,17,17,20,24,30}; // 假定數據較小,對應價格int len;int memory[11]; // 記錄 int record[11]; // 在哪里切割int min = -1;
};int main()
{Solution a(4);std::cout <<a.fun() << std::endl;
}
)
)
