复习（7）19章内容

吾家有女初长成，雄威玲珑八面风

算法

这里说一下对最后一句话的了解，所谓的决策序列中包含最优子序列，也就是你的决策必须使得整个决策过程看上去代价最小，而贪心算法，实际上只要局部代价最小就可以了
接下来分析一下背包问题

586433.png
786454.png
关键：在此步的时候，以后的决策和方案也必须是最优的
78564563544.png

具体的过程：如果是最后一个，并且权重够的话，那么就选定，否则的话就不选
当前如果还有多个，而权重不够，则就等于后面的背包进行选择的最大值
如果是可以选择，那么应该做的是选择之后加上剩下的最大选择和不选之后接下来的最大值两者中较大的一个
再看看弗洛伊德算法

56754.png
123214435.png
12312321323.png
213231223.png
clipboard.png123.png
clipboard.png12334253.png
……
嗯，没什么要说的
clipboard.png123123.png
这么理解，既然对于每次ij边的考虑都是在遍历到了k点做考虑的，那么规定（不经过超过k的点，其实没什么意义）
clipboard.png21323.png

一开始，对于所有的两点来说，距离都被初始化，随后，因为还没有经过任何的点，所以最大的k值始终都是0

12312321.png
即时进行更新
clipboard.png