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

Zedd

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

    由于我学习《算法导论(第三版)》这本书，更多的是应用于解制造业的工程问题，不是用于IT行业，所以针对数据结构这一块儿，不作为我的重点部分，我只做基本了解，不做深入学习，所以选择性跳过，若今后有遇到相关工程问题，再补该方面知识。
; {$ n! l8 p& B9 D' G1 u
针对本书关于钢条切割方面的讨论，涉及起始取地址从0开始，由于MATLAB本身语法限制，在相同思想下，将代码进行了适当修改。
! o5 |0 t7 |2 h1 i) t/ ~7 h
4 k3 o$ l, Y7 \, j2 ?% s: ~朴素递归算法解钢铁切割问题：
$ C" y, e2 h& O2 M9 t

• 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)%动态规划算法 自底向上
  7 G% L, I8 g8 J1 J  h" j) f" P

8 L' I/ W4 U: y# s5 `* y2 h: r

朴素递归算法：

• 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
  

) Z' J( `$ W( v: T2 F
( Q% y9 I% d) L" n. Z9 ?& A
动态规划算法：
/ z# h# o- m7 t/ M7 {

• 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
    T2 W) R3 e! ]1 m! K" f" s

/ X( s# l5 T% t7 j

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

wu68aq

研究研究。