算法题-背包问题-核心

此文章绝大部分非原创，大部分来源于背包九讲和宫水三叶的题解

背包九讲的文章地址

背包问题

现有n个物品，这n个物品各自的重量用weight数组表示，这n个物品的价值用value数组表示，现在你有一个最大承重为W的背包，每个物品只有一个，问：如何装物品，才能让背包里的物品的价值最大化。

比如： 现有三个物品，weight数组是[1,3,4]，value数组为[15,20,30]，背包承重为4。

解析过程

背包问题本质还是dp，所以

f[n][W]：代表从n个物品中挑选，放入最大承重为W的背包中，得到的最大价值。

f[3][4]：代表从3个物品中挑选，放入最大承重为4的背包中，得到的最大价值。

dp本质是将一个大规模的问题转换成一个小一点规模的问题。

那现在规模是n和W，现在怎么转换成规模更小的问题呢，是将n缩小还是将W缩小呢？

规模缩小的思路确实很难想，但如果反向思考，从将规模扩大的角度去思考。

比如：

已知f[2][4]：从两个物品weight:[1,3]和value:[15.20]中挑选装入承重为4的背包中的最大价值为35。

现在背包大小依旧为4，然后能从两个物品换成三个物品，也就是多了一个物品（起名为addItem）w:[4]，v:[30]，

这样问题就从f[2][4]变成了f[3][4]，

请再看这句话：f[n][W]：代表从n个物品中挑选，放入最大承重为W的背包中，得到的最大价值。

那么这个addItem的添加对f[2][4]有没有影响呢？

如果我没有把addItem放入背包，那么很明显f[3][4] = f[2][4].

如果我把addItem放入了背包，那么问题就转换成了求从两个物品w:[1,3]，v:[15.20]中挑选装入承重为0的背包的最大价值问题，即f[3][4]的问题转换成了f[2][0]

然后f[3][4]就是max(f[2][4], f[2][0] + value[3])

也就是说：f[i][j]的问题都能转换成f[i-1][j]和f[i-1][j - weight[i]] + value[i]

即f[i][j] = max(f[i - 1][j],f[i - 1][j - weight[i]] + value[i])这就是dp的状态转换方程。

图解

三个物品，weight数组是[1,3,4]，value数组为[15,20,30]，背包承重为4。

构造一个二为数组，物品个数做行，背包大小做列，表格内容为当前的最大价值

根据我们的状态转移方程得知：当我们求二维数组中的某一个时，比如f[2][4]，取决于f[1][4]和f[0][1]

而且求某一列时，比如第二列，完全取决于第一列。

也就说我们不需要用一个二维数组来实现，只需要一个一维数组

核心掌握

背包问题：现有n个物品，这n个物品各自的重量用weight数组表示，这n个物品的价值用value数组表示，现在你有一个最大承重为W的背包，每个物品只有一个，问：如何装物品，才能让背包里的物品的价值最大化。

这是一个关于重量、价值的问题，我们把重量换成成本，把价值换成收益。

那么这个背包问题核心就是两个单词成本、收益。

即有n个东西，这n个东西的各自的成本用cost数组表示，这n个东西的收益用profit数组表示，现在你只有C的成本，求能得到的最大收益是多少。

而背包问题的状态转换思想是：f[n][C]能转换成f[n-1][C]（不选中第n个东西）和f[n-1][C-cost[n]] + profit[n]（选中第n个东西），请一定要理解这句话，并且牢记。

对应的状态转换方程：f[n][C] = max(f[n-1][C], f[n-1][C - cost[n]] + profit[n])

画二维数组只是为了理解背包问题，我很不推荐用二维数组去套用类背包问题。

背包问题本质是动态规划，动态规划本质就是状态转换，而背包问题特殊的状态转换才是背包问题的特征，而这特性我下面会讲。

类背包问题

leetcode上没有纯粹的背包问题，都是类背包问题，而背包问题的特性（或者说核心），即成本、收益。

如果我们能从一个类背包问题中，抽象出成本和收益，并且这个问题能表达成下面这句话：

即有n个东西，这n个东西的各自的成本用cost数组表示，这n个东西的收益用profit数组表示，现在你只有C的成本，求能得到的最大收益是多少。

那么就能用背包问题去解。

然后套用f[n][C] = max(f[n-1][C], f[n-1][C - cost[n]] + profit[n])即可

比如：这道题

• 总成本是m=5，n=3。简写成C：[5,3]，
• 收益是最大子集的长度
• 数组中每个item的成本是cost：[[1,1],[3,1],[2,4],[0,1],[1,0]]
• 数组中每个item的收益是profit：[1,1,1,1,1]

能表达成：

有len个item，每个item的成本是[0的个数,1的个数]，每个item的收益是1，现有总成本[0的最多次数:4,1的最多次数:3]，求最长子集的长度。

完美的背包问题：

直接套用f[len][m][n] = max(f[len-1][m][n],f[len-1][m-zeroCount(list[len])][n-oneCount[list[len]])

比如：这道题

我们用官方的第二个例子来举例

• 总成本是needs中的每一个：needs[0]：1，needs[1]：2，needs[2]：1。简写成C：[1,2,1]
• 收益是最低价格
• 每个礼包的成本是cost：[[1,1,0]，[2,2,1]]
• 每个礼包的收益是profit：[4,9]

能表达成

i个数组，每个item的成本是[A的个数,B的个数,C的个数...]，每个item的收益是[该礼包的花费]，总成本是[A必须买的个数，B必须买的个数，C必须买的个数...]

也是完美的背包问题

状态转换的核心思想依旧是选与不选

f[i][needs[0]][needs[1]]...[needs[last]] = max(f[i-1][needs[0]][needs[1]]...[needs[last], f[i-1][needs[0] - cost[i][0]][needs[1] - cost[i][1]]...[needs[last] - cost[i][last] + cost[i][last])