背包问题四种不同算法的实现(共25页).doc

精选优质文档-倾情为你奉上兰州交通大学数理与软件工程学院题 目 0-1背包问题算法实现院 系 数理院 专业班级 信计09 学生姓名 雷雪艳 学 号 指导教师 李秦 二一二年 六 月 五 日一、问题描述： 1、01背包问题：给定n种物品和一个背包，背包最大容量为M，物品i的重量是wi,其价值是平Pi，问应当如何选择装入背包的物品，似的装入背包的物品的总价值最大？背包问题的数学描述如下：2、要求找到一个n元向量(x1，x2xn)，在满足约束条件：情况下，使得目标函数，其中，1in；M0；wi0；pi0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解1。 给定n 种物品和1个背包。物品i 的重量是wi，其价值为pi，背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择