《算法导论(第三版)》第十五章，动态规划

Zedd · 发表于 2020-3-9 17:40

EDA365欢迎您登录！

您需要登录才可以下载或查看，没有帐号？注册

x

《算法导论(第三版)》第十五章，动态规划

由于我学习《算法导论(第三版)》这本书，更多的是应用于解制造业的工程问题，不是用于IT行业，所以针对数据结构这一块儿，不作为我的重点部分，我只做基本了解，不做深入学习，所以选择性跳过，若今后有遇到相关工程问题，再补该方面知识。

针对本书关于钢条切割方面的讨论，涉及起始取地址从0开始，由于MATLAB本身语法限制，在相同思想下，将代码进行了适当修改。

朴素递归算法解钢铁切割问题：

clear;clc
p=[1 5 8 9 10 17 17 20 24 30];
CUT_ROD(p,4)%朴素递归算法自顶向下
[r s]=EXTENDED_BOTTOM_UP_CUT_ROD(p,10)%动态规划算法自底向上
" f9 \/ S @1 p+ N2 o7 Y$ s

朴素递归算法：

function [q] = CUT_ROD(p,n)
%自顶向下递归实现钢铁切割问题《算法导论》第十五章动态规划
%算法思想：将钢铁分为左右两段，左段不切，为收益最大值，右段一直切，直到切完。
if n==0%右段已切完
q=0;
return;
end
q=-inf;%收益从负开始
for i=1:n
q=max([q,p(i)+CUT_ROD(p,n-i)]);%寻求是否切的最大收益
end
end
2 `1 ]1 H' j0 [& S( ~ O% t$ j7 b

动态规划算法：

function [r,s] = EXTENDED_BOTTOM_UP_CUT_ROD(p,n)
%动态规划：自底向上
r=p;%初始化不切割为最大收益
s=1:n;%初始化不切割为最大收益的切割方式
for j=2:n
for i=1:j-1%去掉i==j的情况，不需要跟本身作比较
if r(j)<p(i)+r(j-i)
r(j)=p(i)+r(j-i);
s(j)=i;
end
end
end
end
6 r1 z9 h' s/ Q4 X2 _) {5 K" ]

在解决取地址从0开始的问题时，突然想到，假设将初始切割方案直接默认为为不切割方案，将比书中的效果更佳。

wu68aq · 发表于 2020-3-9 18:52

研究研究。

帐号		自动登录	找回密码
密码			注册

《算法导论(第三版)》第十五章，动态规划

EDA365欢迎您登录！

浏览过的版块

推荐内容 /1