动态规划DP
-
一般DP的组成
一般DP主要分为两个部分:表示状态,状态转移
这里以P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles为例- 表示状态
答案为从上到下的路径上的最大权值和,那么我们就可以设计\(f[i][j]\)为从最底端出发走到\((i, j)\)可以取到的最大权值和
那么显然,\(f[1][1]\)的最大值为我们所要的答案 - 状态转移
那么我们很快可以确定\(f[n][i]\)的值就等于\(a[n][i]\),这也是目前我们唯一可以迅速得出的\(f\)值
那么我们从这个值推导其他的\(f\)值,不难发现,\((i, j)\)的\(f\)值等于下一层所有可以到达\((i, j)\)的位置中对应的最大\(f\)值与\(a[i][j]\)的和,那么不难得出状态转移方程:
- 表示状态
-
背包DP
-
01背包
对于\(m\)个物品,都有着对应的代价\(w[i]\)和价值\(v[i]\),我们可以消耗代价获得对应的价值,且每个物品的价值只能被获得一次,求消耗不超过\(t\)的代价所能获得的最大价值。
那么,我们有\(dp[i][j]\)描述只考虑前\(i\)个物品且剩余总代价为\(j\)时,所获得的价值最大值
显然,对于一个物品,我们只有两种选择,买与不买,那么我们显然要在这两种情况之间选一个最大值转移到下一个状态-
对于不买此物品
总价值等于只考虑到上一个物品的最大价值,即\(f[i - 1][j]\) -
对于买此物品
我们的剩余总代价减少了,但与此同时我们获得了此物品的价值,总价值为\(f[i - 1][j - w[i]] + v[i]\)
那么,有状态转移方程
\[f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]]+v[i]) \]不难看出,这样的状态表示是极其低效的,因为我们只需要用到\(i - 1\)的状态,所以我们可以压掉第一维,并从大到小枚举\(j\),因为状态转移只会用上\(f[j - w[i]]\)和\(f[j]\),而\(j - w[i]\)和\(j\)又都不大于\(j\),所以这样可以确保当我们计算\(f[j]\)时,\(f[j - w[i]]\)和\(f[j]\)的状态仍停留在只考虑前\(i - 1\)个物品的状态,确保每一个物品都只被取一遍
-
-
点击查看代码
for(int i=1; i <= n; ++i)
for(int j = t; j >= w[i]; --j)
f[j] = max(f[j], f[j-v[i]] + w[i]);