算法分析与设计实验报告之01背包问题(共20页).doc

精选优质文档-倾情为你奉上算法分析与设计实验报告0/1背包问题0/1背包问题的不同算法解决方案组员黄希龙 张育强周麒目录一.问题描述0/1背包问题:现有n种物品，对1=i=n，已知第i种物品的重量为正整数Wi，价值为正整数Vi，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分）二.算法分析根据问题描述，可以将其转化为如下的约束条件和目标函数：于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量。首先说明一下0-1背包问题拥有最优解。假设是所给的问题的一个最优解，则是下面问题的一个最优解：。如果不是的话，设是这个问题的一个最优解，则，且。因此，这说明是所给的0-1背包问题比更优的解，从而与假设矛盾。1.穷举法：用穷举法解决0-1背包问题，需要