7.2 动态规划

7.2 动态规划 — iEDA 开源文档与工程实践。

本目录内容

连接x1,x2的线段，如果包括x1,x2端点则称为闭线段，不包括则称为开线段。数学上表述为，任取线段内部的某一点x，如果能写出/描述出这点x的轨迹或其坐标变化的规律，

区间DP的特征 : 可以两个或多个部分进行整合, 或者反过来；能将问题分解为能两两合并的形式. 区间DP的求解 : 对整个问题设最优值，枚举合并点，将问题分解为左右两个…

这里我们就可以直接列出一个是0-1规划的方程，设的变量xi，“1”表示被选中，“0”表示没被选中

7.2.3 树形DP — iEDA 开源文档与工程实践。

常用的运算符共 6 种，分别为与（ & ）、或（ | ）、异或（ ^ ）、取反（ ~ ）、左移（ << ）和右移（ >> ）

有N种物品，第i种物品的体积是Ci，价值是Wi，每种物品的数量都是有限的，为Ni。现有容量为V的背包，放入若干物品，在总体积不超过V的条件下，使总价值尽可能大。