美文网首页
钢条切割(算法导论)

钢条切割(算法导论)

作者: E7_5399 | 来源:发表于2020-11-12 18:35 被阅读0次

    Serling公司出售一段长度为i英寸的钢条价格为pi(i=1,2,3...),钢条只能切割为整英寸。

    长度i 1 2 3 4 5 6 7 8 9 10
    价格pi 1 5 8 9 10 17 17 20 24 30

    切割问题是这样的,给定一张价格表,和长度为n的原始钢条,求能够产生的最大收益值rn(可任意整英寸切割或者不切)。


    思考:

    拿到一根n英寸的钢条,第一刀就有n种切法(最左边表示没切),之后就会变成2条钢条。比如从3的位置切,这样收益就变成了rn = f(n) = 8+f(n-3),这样用递归的方式就可以得到结果,递归+中间结果缓存=动态规划,只不过是自顶向下的方式。还有一种更好的方式是自底向上,类似斐波拉切数列,将子问题按规模排序依次求解。

    代码(自顶向下):

    #include <iostream>
    #include <vector>
    
    using std::vector, std::cout, std::endl;
    
    class Solution {
    private:
        vector<int> memo;
    
    public:
        int do_cut(const vector<int>& tb, int n) {
            auto max = tb.at(n-1);
    
            // 最小子问题
            if (1 == n) { return tb[0]; }
    
            for (auto i = 1; i < n; ++i) {
                int sub_max;
    
                if (0 == memo.at(n-i)) {
                    // 缓存子问题结果
                    memo[n-i] = sub_max = do_cut(tb, n-i);
                } else {
                    sub_max = memo.at(n-i);
                }
                max = std::max(tb.at(i-1) + sub_max, max);
            }
    
            return max;
        }
    
        int cut_rod(const vector<int>& tb, int n) {
            memo.resize(tb.size(), 0);
    
            return do_cut(tb, n);
        }
    };
    
    int main() {
        vector<int> prices {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
        Solution s;
    
        for (auto i = 1; i < 11; ++i) {
            cout << s.cut_rod(prices, i) << endl;
        }
    
        return 0;
    }
    

    你也可以试试自底向上的方式,留言告诉我。

    相关文章

      网友评论

          本文标题:钢条切割(算法导论)

          本文链接:https://www.haomeiwen.com/subject/xibpbktx.html