算法“动态规划”最佳实践——背包问题

鲁迅曾说：“有人相爱，有人夜里看海，有人动态规划怎么都写不来。” 足以证明动态规划的难度，要想更好地学习动态规划，“背包问题”首当其冲，其被称之为动态规划的最佳实践，今天咱就来好好说说“背包问题”。

一、动态规划介绍

(1) 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法

(2) 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

(3)与分治法不同的是，适合于用动态规划求解的问题，经分解得到的问题往往不是互相独立的。 ( 记下一个子阶段的求解是建立在上一个子阶段的求解的基础上，进行进一步的求解 )

(4) 动态规划可以通过填表的方式来逐步推进，得到最优解。

二、背包问题介绍

(1) 要求达到的目标为装入的背包的总价值最大，并且重量不超出。

(2) 要求装入的物品不能重复。

(3) 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选 择物品放入背包使物品的价值最大。其中又分 01 背包和完全背包(完全背包指的 是：每种物品都有无限件可用)

(4) 这里的问题属于 01 背包，即每个物品最多放一个。而无限背包可以转化为 01 背 包。

(5) 算法的主要思想，利用动态规划来解决。每次遍历到的第 i 个物品，根据 w[i]和 v[i] [j] 来确定是否需要将该物品 放入背包中。即对于给定的 n 个物品，设 val[i]、 w[i]分别为 第 i 个物品的价值和重量，C 为背包的容量。再令 v[i][j] 表示在前 i 个 物品中能够装入容量为 j 的背包中的最大价值。

三、思路分析及代码实现

如图二维表用v[i][j]表示，i为物品的索引号，j为背包的称重量，要找到最大价值所放的物品，只需三个核心步骤：

① 第一行和第一列全部设置为0，即：v[0][j] = 0; v[i][0] = 0; 当然，可以不用设置，因 为int数组默认值为0.

② 当w[i] > j 时，v[i][j] = v[i-1][j]; // 取上一行j列的值。

③ 当j >= w[i] 时, v[i][j] = Math.max(v[i-1][j], val[i-1] + v[i-1][j-w[i-1]]);

分析完我们用代码来实现一下：

我们可以看到，我们获取了所有物品放置的表，现在只需找出最大值及其放入的物品是哪些即可。

思路：定义一个二维数组int[][] path; 用来实时记录每次更新最大值时的表格位置标记为1, 然后找到最后一个1所在的位置，用背包重量j减去当前行所对应的商品的重量w[i-1], 返回上行寻找此重量下的最早更新j-w[i-1]承重下的最大价值即可。

核心代码：

背包问题的讲解就到此结束了，如果有不懂的可以在评论区留言，我会来解答；如果喜欢我的作品或者觉得讲的好的朋友可以转发点赞支持一下，谢谢大家的收看。