江苏龙网

  1. 首页 > 人文 > >

算法萌新如何学好动态规划（3）( 二 )


确定「DP 状态」后 ， 我们来考虑「DP 转移方程」是什么 。
对于第 i 个物品来说 ， 它只有两种状态 ， 即要么取 ， 要么不取 。 如果不取第 i 个物品 ， 则
算法萌新如何学好动态规划（3）文章插图
；如果取第 i 个物品 ， 则
算法萌新如何学好动态规划（3）文章插图
， 因此我们得到如下「DP 转移方程」：
算法萌新如何学好动态规划（3）文章插图
其中初值
算法萌新如何学好动态规划（3）文章插图
为负无穷 ， 其中
算法萌新如何学好动态规划（3）文章插图
， 最终答案为
算法萌新如何学好动态规划（3）文章插图
， 代码如下所示 。
int DP() {for(int i = 1; i <= M; i++)f[0][j] = -inf; // 负无穷 ， inf 可以为 1e8f[0][0] = 0;for(int i = 1; i <= N; i++)for(int j = 0; j <= M; j++)if(j >= v[i])f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]);elsef[i][j] = f[i-1][j];int ans = 0;for(int i = 0; i <= M; i++)ans = max(ans, f[N][i]);return ans;}观察上述代码 ， 不难发现 ，
算法萌新如何学好动态规划（3）文章插图
仅由
算法萌新如何学好动态规划（3）文章插图
和
算法萌新如何学好动态规划（3）文章插图
决定 。 这就给了我们一个思考角度 ， 即能否将二维数组 f 的第一维去掉？
答案显然是可以的 ， 我们可以倒序枚举 j ， 使得更新
算法萌新如何学好动态规划（3）文章插图
时
算法萌新如何学好动态规划（3）文章插图
还未被更新 ， 即
算法萌新如何学好动态规划（3）文章插图
代表的实际是
算法萌新如何学好动态规划（3）文章插图
的值 。 这样说可能不好理解 ， 我们先看一下优化后的代码：
int DP() {for(int i = 1; i <= M; i++)f[j] = -inf; // 负无穷 ， inf 可以为 1e8f[0] = 0;for(int i = 1; i <= N; i++)for(int j = M; j >= v[i]; j++)f[j] = max(f[j], f[j-v[i]] + w[i]);int ans = 0;for(int i = 0; i <= M; i++)ans = max(ans, f[i]);return ans;}根据上述代码 ， 我们不难发现在第 i 轮 ， 更新到
算法萌新如何学好动态规划（3）文章插图
时 ，
算法萌新如何学好动态规划（3）文章插图
与
算法萌新如何学好动态规划（3）文章插图
代表的都是第 i - 1 轮的值 ， 即
算法萌新如何学好动态规划（3）文章插图
与
算法萌新如何学好动态规划（3）文章插图


推荐阅读


上一篇：新人必看，一个接触币圈2年的人花钱买来的教训

下一篇：MIUI 12.5开启内测报名：首批支持21款机型！今晚发布后开始推送