经典动态规划

一件物品和第二件物品，在重量没有超出背包容量下，所选价值最大。

如果每种物品只能选 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

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

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

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

解题思路

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

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

状态

何为状态?

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

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

• 背包容量
• 可选的物品

题目要求的是在满足背包容量前提下，可装入的最大价值。

那么我们可以根据上述状态定义出 dp 数组，即：

dp[i][w] 表示：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]

我们自然而然的考虑到如下特殊情况：

当 i = 0 或 w = 0，那么：

dp[0][...] = dp[...][0] = 0

解释：

对前 0 个物品而言，无论背包容量等于多少，装入的价值为 0;

当背包容量为 0 时，无论装入前多少个物品(因为一个都装不进去)，背包里的价值依旧为 0。

根据这个定义，我们求的最终答案就是dp[N][W]

我们现在找出了状态，并找到了 base case，那么状态之间该如何转移呢(状态转移方程)?

状态转移方程

dp[i][w] 表示：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]。

思考：对于当前第 i 个物品：

• 如果没有把第 i 个物品装入包里(第 i 个物品质量大于当前背包容量)：那么很显然，最大价值dp[i][w]应该等于dp[i - 1][w]，没有装进去嘛，故当前背包总价值就等于之前的结果，即第i - 1 个物品之前的总价值 。
• 如果把第 i 个物品装入了包里，那么 dp[i][w]应该等于什么呢?

它应该等于下面两者里的较大值：

1. dp[i - 1][w] //前i - 1个物品，背包所装的最大价值
2. dp[i - 1]w - wt[i]] + val [i] //当前第 i 个物品我装里边了，那么此时背包装入的总价值即为：当前第 i 个物品的价值 val [i] + 第 i 个物品之
3. 

（编辑：泉州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!