实验三 01 背包问题不同算法设计、分析与对比 一．问题描述 给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包的容量为 c。 问题：应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 说明：在选择装入背包的物品时，对每种物品 i 只有两个选择，装入背包或不装入背包，也不能将物品装入背包多次。 二．实验内容与要求 实验内容： 1.分析该问题适合采用哪些算法求解（包括近似解）。 动态规划、贪心、回溯和分支限界算法。 2.分别给出不同算法求解该问题的思想与算法设计，并进行算法复杂性分析。 动态规划： 递推方程： m(i,j) = max{m(i-1,j),m(i-1,j-wi)+vi} j >= wi; m(i-1,j) j < wi; 时间复杂度为O(n). 贪心法： 算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。但是，贪心法当在只有在解决物品可以分割的背包问题时是正确的。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 用贪心法设计算法的特 点 是一步 一步 地 进行，根 据 某个优化 测 度（可能是目标 函 数 ，也可能不是目 标 函 数 ），每一步 上都 要保 证 能获 得局部最优解。每一步只考虑一个数 据 ，它的选取应满 足 局部优化 条件。若 下 一个数 据 与部分最优解连在一起 不再 是可行解时，就不把 该数 据 添 加 到 部分解中， 直 到 把 所有数 据 枚 举 完 ，或者 不能再 添 加 为止 。 回溯法： 回溯法：为了 避 免 生 成 那些不可能产 生 最佳 解的问题状 态，要不断 地 利 用限界函 数 (bou nding fu nction)来处 死 那些实际 上不可能产 生 所需 解的活 结 点 ，以减 少 问题的计算量。这 种具 有限界函 数 的深 度优先 生 成 法称 为回溯法。 对于有n种可选物品的0/1 背包问题，其解空间由长度为n的0-1 向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。 时间复杂度为：O(2n) 空间复杂度为：O(n) 分支限界算法： 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，...
VIP
