如果每种物品只能选 0 个或 1 个(即要么将此物品装进包里要么不装)，则此问题称为 0-1 背包问题;如果不限每种物品的数量，则称为无界(或完全)背包问题。

今天这篇文章我们只关注 0-1 背包问题，下一篇文章再聊完全背包问题。

那我们是如何选择要装入的物品的?

思路初探

首先，质量很大价值很小的物品我们先不考虑(放着地主家金银财宝珍珠首饰不偷，背出来一包煤…，那也就基本告别盗窃行业了…)

然后呢?再考虑质量大价值也大的?还是质量较小价值也稍小的?

我们自然而然想到：装价值/质量 比值最大的，因为这至少能说明，此物品的“价质比”最大(也即贪心算法，每次选择当前最优)

那么这样装能保证最后装入背包里的价值最优吗?

我们先来看一个例子：

假设有 5 个物品，N = 5，每种物品的质量与价值如下：

• W : 20, 30, 40, 50, 60
• V : 20, 30, 44, 55, 60
• V/W: 1, 1, 1.1, 1.1, 1

背包容量为 100

如果按上述策略：优先选“价质比”最大的：即第三个和第四个物品

• 此时质量：40+50=90
• 价值：44+55 =99

但我们知道，此题更优的选择策略是：选第一个，第二个和第四个

• 此时质量：20+30+50=100
• 价值：20+30+55=105

所以，我们的“价质比”这种贪心策略显然不是最优策略。

读过一文学懂动态规划这篇文章的读者会发现，之前文章中兑换零钱例子我们最开始也是采取贪心策略，但最后发现贪心不是最优解，由此我们引出了动态规划。

没错，今天这题也正是动态规划又一经典的应用。

解题思路

根据动之前的文章我们知道，动态规划的核心即：状态与状态转移方程。

那么此题的状态是什么呢?

状态

何为状态?

说白了，状态就是已知条件。

重读题意我们发现：此题的已知条件只有两个：

• 背包容量
• 可选的物品