微信公众号做网站卖东西/重庆发布的最新消息今天

前言：

好久没写0-1背包问题了，都有些不记得了，写这篇文章给自己以后做简单参考，如果能同时帮到读者，不胜荣幸。

正文

0-1背包问题是这样的一个问题，假设有一个背包，其容量为 capacity 。在地上有一堆物品，其数量为 n ，每个物品有两种属性：重量 w和价值 v。

要求就是，找到一个物品的组合，使得它们的重量小于等于最大容量，并且其价值最大。

动态规划的思路解0-1背包问题：

首先建立一个二维数组dp，其中dp[i][j]表示仅使用前i个物品的情况下，当背包容量为j时，所能获得的最大价值。也即：从前i个物品里面选取一些物品，这些物品的总重量小于等于j，但是它们的价值之和最大，这个最大价值和就记为dp[i][j]。

dp的行宽为n，表示总共有n个物品，列宽为capacity，表示背包的最大容量为capacity。

大致是这样： 

假设有n个物品，并用1-n分别给各个物品编号，wi，vi分别表示第i个物品的重量和价值。

那么第一行的第j列表示，当仅使用物品1、背包容量为j时，所能装进背包里面的最大价值。

所以，在第一行当中：

（1）若w1 > j，那么背包容量j是无法容纳第一个物品的重量的，此时应填0

（2）若w1 <= j，那么背包容量是可以容下第一个物品的重量的，此时应填v1.

所以第一行的元素只能填0或者v1，而且前半段是0，后半段是v1

假设n==10，背包容量为3（最终容量）

1,2,3（各个物品的编号）

2,7,1（各个物品的重量）

1,2,3（各个物品的价值）

假设w1==7，那么第一行如下：

设i>1，那么对于第i行的第j列，应该这么填：

（1）wi > j时，那么即使把背包里面已经装进去的东西全部腾空，也不足以装下第i个物品。

此时dp[i][j] = dp[i-1][j]。也就是说，考虑前i个物品和前i-1个物品是一样的结果。

（2）wi <= j时，可以考虑把第i个物品放进去

        （2-1）假如要把第i个物品放进去，那么第i个物品会占据wi的容量，剩下的容量最大能装多少价值的物品呢？毫无疑问，应该最大能装dp[i-1][j-wi]的价值，这是因为dp[m][n]就表示仅使用前m个物品，在容量为n时所能装入的最大价值。也即dp[i][j] = dp[i-1][j-wi] + vi。

        （2-2）假如不把第i个物品放进去，那么价值总量维持不变，也即：dp[i][j] = dp[i-1][j]。

          (2-3)

          那到底要不要把第i个物品放进去呢？有人可能会说，既然能放进去，那为什么不放进去呢？

          放进去的话，价值不是更大吗？事实上不一定，因为这里所说的能放进去是指，把背包里面

          已经放进去的东西腾空后，第i个物品能放进去。但是强行把第i个物品放进去之后，有可能

          导致原来已经放进去的某些物品被挤得没有空间放了，这就有可能导致总价值量的减小。

          所以，当wi <= j时，dp[i][j] = max{dp[i-1][j-wi] + vi ,  dp[i-1][j]}

所以最终填表就是：

 所以，从表格中可以看出来，当背包容量为3，物品个数为3，

各个物品编号为：1,2,3

各个物品重量为：2,7,1

各个物品价值为：1,2,3时，

能装进背包里面的最大价值为4（表格右下角的数）

练习：

这张图片是力扣上面的题目，也是0-1背包问题

 写在最后：如有错误，敬请指正，礼貌交流，感激不尽。