用蛮力法、动态规划法和贪心法求解01背包问题(共19页).doc

精选优质文档-倾情为你奉上算法设计与分析项 目 名 称：用蛮力法、动态规划法和贪心法求解0/1背包问题作者姓名：余武丹李红波刘红梅完成日期：2013年9月20日目录第1章 ：简介（Introduction）第2章 ：算法定义（Algorithm Specification）第三章：测试结果（Testing Results）第四章：分析和讨论第1章 ：简介（Introduction） 0/1背包问题是给定n个重量为w1, w2, ,wn、价值为v1, v2, ,vn的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：