每天进步一点点之（回溯算法，贪婪算法和背包问题）（三）

每天进步一点点之（回溯算法，贪婪算法和背包问题）（三）

==转载链接—从零开始学回溯算法----houjingyi233----/net/qq_32400847/article/details/51474105

解题一般步骤
1.定义一个解空间，它包含问题的解；
2.利用适于收索方法组织解空间
3.利用深度优先收索解空间
4.利用限界函数避免移动到不可能产生解的子空间
著名的四色定理就是指每个平面地图都可以只用四种颜色来渲染

==接下来是动态规划–链接—51148917
动态规划是运筹学的一个分支，是求解决策过程中最优化的数学方法，把多个阶段的过程转换为一系列单阶段问题利用各阶段之间的关系逐个求解。
解题的一般步骤：
1.找出最优解的性质，刻画出其结构特征和最优子结构的特征
2.递归地定义最优解，刻画原问题解和子问题解间的关系
3.以自底向上的方式计算出、各个子问题，原问题的最优解，并避免子问题的重复计算
4.根据最优解时得到的信息，构造最优解

–转载自博客—荷叶田田_------【回溯法–01背包问题--------

01背包问题属于找最优解问题，用回溯法需要构造解的子集树。对于每个物品i，只有选和不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一颗解空间树：其基本思想就是遍历这棵树，以枚举所有情况，最后进行判断，如果重量不超过背包容量，且价值最大的话，这个方案就是最后的答案。
在收索状态空间树时，只要左子节点是一个可行节点，收索就进入其左子树。对于右子树先计算上届函数，以判断是否将其减去（剪枝）

==上界函数bound（）：当前价值cw + 剩余容量可容纳的最大价值 < = 当前最优价值bestp
为了更好的计算和运用上界函数的剪枝，选择先将物品按照其单位重量价值从大到小排序，此后就按照顺序考虑各个物品。
–回溯问题：子集树和排列数
**如果一个问题的解的长度不是固定的，并且解和元素顺序无关，即可以从中选着0或多个，那么解空间的个数是指数级别的，为2的n次幂。

**在递归函数BackTrack中：
当i>n时算法收索到叶子节点，得到一个新的物品装包方案。此时算法适时更新当前的最优价值。
当i<n时当前扩展结点位于排列数的第（i-1层），此时算法选着下一个要安排的物品，以深度优先方式递归的对应的字树进行收索，对不满足上界约束的结点，则剪去相应的字树。
【时间复杂度&&优化】
因为物品只有选和不选2个决策，而总共有n个物品，所以时间复杂度为O(2^n)
因为递归栈最多达到n层，而且存储所有东西的信息只需要常数个一维数组，所以最终的空间复杂度为O(n)