01背包问题四种不同算法的实现VIP专享VIP免费

兰州交通大学 数 理 与软件工程学院 题 目 0 -1 背包问题算法实现 院 系 数理院 专业班级 信计0 9 学生姓名 雷雪艳 学 号 ********* 指导教师 李秦 二Ｏ一二年 六 月 五 日 一、问题描述： 1、0—1 背包问题：给定 n 种物品和一个背包，背包最大容量为 M，物品 i 的重量是 wi,其价值是平 Pi，问应当如何选择装入背包的物品，似的装入背包的物品的总价值最大？ 背包问题的数学描述如下： 2、要求找到一个 n 元向量(x1，x2…xn)，在满足约束条件： 10iiixMwx情况下，使得目标函数pxiimax，其中，1in；M>0；wi>0；pi>0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解[1]。 给定 n 种物品和 1 个背包。物品 i 的重量是 wi，其价值为 pi，背包的容量为 M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i 只有两种选择，即装入背包、不装入背包。不能将物品 i 装人背包多次，也不能只装入部分的物品 i。该问题称为 0-1 背包问题。 0-1 背包问题的符号化表示是，给定 M>0， w i >0， pi >0，1in ，要求找到一个 n 元 0-1 向量向量(x1，x2…xn)， X i =0 或 1 , 1in, 使得 Mwxii ，而且pxii达到最大[2]。 二、解决方案： 方案一：贪心算法 1、贪心算法的基本原理与分析 贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似解。 贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 2、0-1 背包问题的实现 对于 0-1 背包问题，设 A 是能装入容量为 c 的背包的具有最大价值的物品集合，则 Aj=A-{j}是 n-1 个物品 1,2...