本实验报告问题描述:
0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?
背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。在选择物品i装入背包时,可以选择i的一部分,而不一定要全部装入。应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?
Prim算法:一个无向连通图的生成树是一个极小连通子图,它包括图中全部的结点,并且尽可能少的边。遍历一个连通图得到图的一颗生成树。
Kruskal算法:一个无向连通图的生成树是一个极小连
Prim算法的正确性证明
对步数归纳
命题:对于任意 k < n, 存在一棵最小生成树包含算法前 k 步选择的边
归纳基础:k=1, 存在一棵最小生成树 T 包含边e={1,i}, 其中{1,i}是所有关联 1 的边中权最小的.
设T 为一棵最小生成树,假设T 不包含{1,i}, 则T{{1,i}}含有一条回路,回路中关
联1的另一条边为{1,j},
令 T ’=(T-{{1,j}}){{1,i}},
则T’也是生成树,
且W(T ’)W(T).
1
j
i
T
i
1
j
T’