实验三:贪心算法回溯法与分支限界法.docx

本实验报告问题描述: 0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大? 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。在选择物品i装入背包时,可以选择i的一部分,而不一定要全部装入。应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大? Prim算法:一个无向连通图的生成树是一个极小连通子图,它包括图中全部的结点,并且尽可能少的边。遍历一个连通图得到图的一颗生成树。 Kruskal算法:一个无向连通图的生成树是一个极小连