实验三 01 背包问题不同算法设计、分析与对比 一．问题描述 给定 n 种物品和一背包
物品 i 的重量是 wi，其价值为 vi，背包的容量为 c
问题：应如何选择装入背包中的物品，使得装入背包中物品的总价值最大
说明：在选择装入背包的物品时，对每种物品 i 只有两个选择，装入背包或不装入背包，也不能将物品装入背包多次
二．实验内容与要求 实验内容： 1
分析该问题适合采用哪些算法求解（包括近似解）
动态规划、贪心、回溯和分支限界算法
分别给出不同算法求解该问题的思想与算法设计，并进行算法复杂性分析
动态规划： 递推方程： 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)来处 死 那
