01背包问题不同算法设计、分析与对比.doc

实验三 01 背包问题不同算法设计分析与对比 一问题描述 给定 n 种物品和一背包物品 i 的重量是 wi其价值为 vi背包的容量为 c 问题应如何选择装入背包中的物品使得装入背包中物品的总价值最大 说明在选择装入背包的物品时对每种物品 i 只有两个选择装入背包或 不装入背包也不能将物品装入背包多次 二实验内容与要求 实验内容 1.分析该问题适合采用哪些算法求解包括近似解 动态规划贪心回溯和分支