0-1背包问题和部分背包问题的求解 一、简介 背包问题是一个很经典而且讨论很广泛的算法问题了，0-1背包问题和部分背包问题解决方法背后其实隐藏了两种比较常见的算法解决思路，动态规划和贪婪算法。 二、问题描述 假设我们有n件物品，分别编号为1, 2...n。其中编号为i的物品价值为vi，它的重量为wi。为了简化问题，假定价值和重量都是整数值。现在，假设我们有一个背包，它能够承载的重量是W。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？这个问题其实根据不同的情况可以归结为不同的解决方法。假定我们这里选取的物品每个都是独立的，不能选取部分。也就是说我们要么选取某个物品，要么不能选取，不能只选取一个物品的一部分。这种情况，我们称之为0-1背包问题。而如果我们可以使用部分的物品的话，这个问题则成为部分背包(fractional knapsack)问题。 三、数据与问题 有5个物品，其重量分别是{2, 2, 6, 5, 4}，价值分别为{6, 3, 5, 4, 6}，背包的容量为10，求装入背包的物品和获得的最大价值。 请用0-1背包的动态规划和部分背包的贪婪算法分别处理上述问题。