动态规划——背包问题整理（01背包+完全背包）

1、引言

背包问题简单描述，其实就是有一堆物品同时具有一定价值和重量，现有一个背包可以承受最大重量m，那么要怎么选择在不超过背包最大重量的前提下，使背包中选择的物品价值最大。

最常见的背包问题又可以分为：01背包和完全背包，图示如下：

（图片引自：代码随想录）

2、标准01背包分析

（1）问题描述

（2）分析

        最直接的想法应该是暴力解法，每一件物品只存在两种状态，拿或者不拿，那么便可以采用回溯的思想例举出所有可能，然后找到价值最大的组合，但我们会发现时间复杂度就到了O(2^n),n代表物品的种类数。也就是采用暴力解法会带来指数级别的时间复杂度，因此，我们可以考虑采用动态规划来求解。

动态规划五步曲前四步：

1）确定dp含义

        因为同时存在物品种类和背包最大重量，要求组合的最大价值。我们可以采用二维数组表示，即 dp[i][j]，表示从物品0~i中任意取，放进容量为j的背包中，价值总和最大是多少。

2）递推公式

        根据dp的定义，我们可以从两个方向来推导dp:

        不取物品i：从dp[i-1][j]进行推导，即背包的容量为j，里面不放物品i的最大价值。此时的dp[i][j]就是dp[i-1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)

        放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值。

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3）dp初始化

        首先从dp[i][j]的定义出发，如果背包容量j为0的话