典型的01背包问题

//由于这是典型的背包问题我就用背包的方式讲了

题目就是说有N件物品和一个容量为v的背包。放入第i件物品小号的费用是Ci，得到的价值是Wi，要找到一种方法使的放入背包的物品总和最大。

由于每种物品只有一件，只有两种选择：放或者不放。那么我们可以思考：“将前 i 件物品放入容量为 v 的背包中”这个子问题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只和前 i − 1 件物品相关的问题。如果不放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入容量为 v 的背包中”，价值为 F[i − 1, v]；如果放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入剩下的容量为 v − Ci 的背包中”，此时能获得的最大价值就是 F[i − 1, v − Ci] 再加上通过放入第 i 件物品获得的价值 Wi

所以我们可以得到转移方程为dp[i, v] = max{dp[i − 1, v], dp[i − 1, v − Ci] + Wi}

知道了这个方程之后我们很显然知道要开一个大小为v*v的二维数组，我们浅叫这个数组为dp。我们可以看到dp数组需要很大,至少超过2行!那么我们想一想可不可减少行数呢?

首先我们知道,d[i][j]的值只和它的上一种状态有关,即dp[i-1][j],也就是第i行的dp值,只与第i-1行有关,我们通过这条性质,可以将dp数组减少到两行即可,也就是滚动数组优化01背包!

再深入研究发现dp数组可以变成一维，怎么做呢?设dp[v]表示前i种物品(全部物品或者部分物品)放入一个容量为v的背包可以获得的最大价值,这样转移方程就可以写成dp[v]=max(dp[v],dp[v-w[i]]+c[i])

相关题目：

1037：好人卡（01背包）

1064：We don't match each other（好人卡英文版）

1219：大佬买瓜（01背包空间压缩）

1942：17晒衣服（01背包变形）