0-1背包问题详解：如何选择最优物品组合以最大化背包价值

1. 0-1背包问题

0-1背包问题：小偷在商店偷窃时发现了n件物品。第 i 件物品价值 vi 元，重量为 wi 磅，其中 vi 和 wi 为整数。他希望能带走尽可能有价值的东西，但他的背包最多只能装W磅的东西，其中W是整数。您应该随身携带哪些物品？这个问题被称为0-1背包，因为每件物品要么被拿走，要么被留下；小偷不能只拿走一件物品的一部分，也不能拿走同一件物品两次。

注意：在选择放入背包的物品时，每个物品i只有2种选择，即放入背包或不放入背包。物品i不能多次装入背包，也不能仅装入物品i的一部分。（如玉器、花瓶等）

在（分数背包问题）中，场景与上面相同，但是小偷可以拿走部分物品，而不必进行0-1的二元选择。您可以将 0-1 背包问题中的物品视为金锭，而某些问题中的物品更像是金粉。

2.贪心算法（按单位权重值排序）（包括为什么不能解决）

首先声明：虽然两个问题类似，但是我们可以用贪心策略来解决背包问题，但不能用0-1背包问题。为了解决部分背包问题，我们首先计算每种商品每磅的价值vi/wi。按照贪婪策略，小偷首先尽可能多地拿走每磅价值最高的物品。如果所有物品都拿走了，但背包未满，他继续尽可能多地拿走每磅价值第二高的物品，以此类推。直到达到重量上限 W。因此，通过按每磅价值对物品进行排序，贪心算法的运行时间为 O(nlgn)。

对于这个问题，一开始确实是有点困难。有一堆物品，每件物品都有一定的品质和价值。我们可以装载的总重量是有限制的。我们应该如何加载它才能最大化其价值？对于这n项，我们可能会选择也可能不会选择每一项，所以我们总共可能有2^n种组合选择方法。如果我们用这种方法通过硬计算来计算，整体的时间复杂度会达到指数级别，这肯定是不可行的。

现在让我们换个角度思考。既然每件商品都有价格和重量，那么我们是否可以优先考虑单价最高的商品呢？例如下图中，我们有3件商品，它们的重量和价格分别是10、20、30公斤和60、100、120。

所以根据单价，我们首先应该选择价格为60的元素。选择后，背包里还剩下50 - 10 = 40kg。继续前面的选择，我们应该选择价格为100的元素，这样背包里的总价值就是60+100=160。占用的重量是30，剩下20kg。因为后面需要挑选的物品有30kg，已经超出了背包的容量。基于这个想法我们最多可以选择的是前两项。如下图：

按照我们之前的预期，这种选择获得的价值应该是最大的。但由于背包的重量限制，这里只用了30公斤，剩下的20公斤就浪费了。这会是最佳选择吗？让我们看看所有的选项：