回溯法01背包

※※※※只为考试，解释大致意思，如有错误还望海涵！※※※※

有载重量的背包，物体重量分别为5,15,25,27,30，物体价值分别为12,30,44,46,50。求最优装入背包的物体及价值。

1. 为0，计算，大于，生成结点1,2,3,4，部分解(1,1,1,0)；
2. 在结点4计算，大于，继续向下搜索生成结点5，得到价值为86的可行解(1,1,1,0,0)，保存在解向量中， 更新为86；

6.2.1 多段图的决策过程

※※※※只为考试，解释大致意思，如有错误还望海涵！※※※※

多段图的最短路径问题，是求从源点到达收点的最小花费的通路。

数组元素cost[i]：存放顶点i到达收点t的最小花费

数组元素path[i]：存放顶点i到达收点t的最小花费通路上的前方顶点编号

数组route[n]：存放从源点s出发，到达收点t的最短通路上的顶点编号

利用分支界限法求解旅行售货员问题

某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。

最小生成树

Prim 算法计算最小生成树。最小生成树的定义：最小生成树是一副连通加权无向图中一棵权值最小的生成树。假设给定无向图 G 一共有 n 个顶点，那么最小生成树一定会有 n-1 条边。

01背包问题

用动态规划算法实现 0-1 背包问题，在计算机上编程实现。我们有 n 种物品，物品 j 的重量为 wj，价格为 pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为 c。如果限定每种物品只能选择 0 个或 1 个。 有六件物品，体积和价值见下表，背包容量为 25。

求解的思想：

1. 背包容量不足以放下第 i 件物品，只能选择不拿：m[ i ][ j ] = m[ i-1 ][ j ]
2. 背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。
3. 综合以上两种情况可以得到状态转换方程 ：

   f[i,j]=Max{ f[i-1,j-Wi]+Vi( j >= Wi ),f[i-1,j]

多段图问题

若存在一个有向加权图 G，且 G 能分出起点和终点以及中间的 n 的阶段，求起点到终点的最短（长）距离。

利用回朔法求解 0-1 背包问题

我们有 n 种物品，物品 j 的重量为 wj，价格为 pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为 c。如果限定每种物品只能选择 0 个或 1 个。有六件物品，体积和价值见下表，背包容量为 25。

求解思想：

1. 定义问题解空间；
2. 确定易于搜索的解空间结构，该问题的解空间结构为子集树；