问题描述

有n个物品，它们有各自的容量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

b8c3ae5884f34d54a5d23395b16cda1b

假设我们有四个物品，背包的容量为8

物品1的重量为2，价值为3.

…

读了题目我们稍作思考，不难发现，若先不管价值多少，那么每个物品它要么放在背包中，要么不放在背包中。（注意，这个思路很重要，可以说动态规划思路的启蒙点就是这个）。那么我们可以按着顺序把物品1到物品4依次尝试放入背包中。

首先明确几个定义：

value[i]:代表第i个物品的价值

weight[i]:代表第i个物品的体积（重量，体积，容量其实说的是一回事）

j表示为此时的背包容量

dp[i] [j]: 代表在前i个物品中选取物品放入容量为j的背包中，此时所选取的物品的价值之和

例如dp[ i-1 ] [ j ]表示为：在前i-1个物品中的选取物品放入容量为j的背包中，此时所选取的物品的价值之和

再例如dp[ 4 ] [ 8 ]表示为：在前4个物品中的选取物品放入容量为8的背包中，此时所选取的物品的价值之和（这便是上面的例题）

那可以从几个方向可以得到dp[4] [8]呢？也就是从哪几个方向得到这个最大值？

确定递推公式

既然我们要在前4个物品中选，那我们可以不可以从第四个物品开始选起呢？当然可以，这第四个物品放还是不放

不放第i个物品时的最大价值： dp[i-1] [j]
放入第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] }

例如dp[4] [8]=max{dp[3] [8]，dp[3] [8-weight[4]]+value[4]}.

当我们有了递推公式，我们只需要初始化一下数组，然后套公式便可顺理成章地解决问题。

那么如何初始化这个二维数组呢？

初始化二维数组

【注】：

放入第i个物品的时候，得先知道不放第i个物品时背包的容量吧。因此可以写一个等式来理解一下：
放入第i个物品时的最大价值=不放第i个物品时的最大价值+第i个物品的价值
dp[i] [j]是一个二维数组，它的值表示的含义是此时背包可以装入的最大价值
dp[i-1] [j-weight[i]]：0到i-1的物品之间任取物品，放入容量为没有放入第i个物品的背包中，其中j-weight[i]就表示没有放入第i个物品背包的容量，也就是此时背包容量为j，减去第i个背包的重量。

故当前元素可以有正上方和左上方的元素递推出来。