加入收藏 | 设为首页 | 会员中心 | 我要投稿 南通站长网 (https://www.0513zz.cn/)- 专有云、图像技术、经验、数据治理、专属主机!
当前位置: 首页 > 站长资讯 > 外闻 > 正文

他们翻出了1977年的Apple II

发布时间:2021-02-12 18:08:49 所属栏目:外闻 来源:互联网
导读:如上图所示,我们想要求得dp[i][j],需要知道dp|[i-1]|[j-1]和dp[i-1][j]的值。因为只有(i - 1, j - 1) 和 (i - 1, j) 这两个点,才能能走到 (i, j)此时的状态转移方程为 第一种状态转移方程dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + val[i][j] 第

如上图所示,我们想要求得dp[i][j],需要知道dp|[i-1]|[j-1]和dp[i-1][j]的值。因为只有(i - 1, j - 1) 和 (i - 1, j) 这两个点,才能能走到 (i, j)此时的状态转移方程为

第一种状态转移方程dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + val[i][j]

第二册中状态转移方程dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + val[i][j]

从这里可以知道我们的状态定义不一样,我们的转移方程就很不一样吧

  • 正确性证明

数学归纳法通常采用三步走的方式,常用的正确性证明方法为数学归纳法。

第一步,第一个阶段所有dp值可以轻松获得,也就是初始化dp[1][1],等于val[1][1]

第二步,假设如果第i-1阶段的所有状态值都正确得到,那么根据状态方程dp[i][j]=max(dp[i - 1][j], dp[i - 1][j + 1]) + val[i][j] 来说,此时就可以计算得到第i阶段中的素有状态值

第三步:得出结论,所有的状态值计算正确

我们继续分析动态规划问题中的0/1背包问题,通常分为三类,0/1背包问题,完全背包问题和多重背包问题。

0/1背包问题是另外两种背包问题的基础,简单描述一下,假设有个背包,载重上限为W,此时有n个物品,第i个物品的重量是wi,价值为vi,那么在不超过背包重量上限的前提下,能获得的最大物品价值总和?同样我们采用四步走的方式

  • 状态定义

首先分析背包问题中的自变量和因变量,其中因变量比较好确定,就是所求最大价值总和,自变量呢,在此自变量为物品种类和背包承重上限,因为这两者会影响价值总和的最大值,所以我们设置一个二维状态。dp[i][j]代表使用前i个物品,背包最大载重为j的情况下最大价值总和。

  • 状态方程

说白了就是找映射函数,dp[i][j]的表达式。我们将dp[i][j]分为两大类,第一类是不选择第i个物品最大价值和,第二类为选择了第i个物品的最大价值和。然后在两者中选择最大值就是价值更大的方案。

如果选择第i个物品,此时的最大价值为dp[i-1][j-wi]+vi,既然选择了第i个商品,那么就需要留出一个位置,那么此时对于剩余的i-1个商品的载重空间就只剩下j-wi了,此时i-1个物品选择的最大价值和为dp[i-1][j-wi],然后加上vi就是当前获得最大价值和。所以转移方程为

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

  • 正确性证明

首先dp[0][j]=0,意味着没有物品的时候,无论背包限重多少,能够得到的最大价值和都是0,所以k0争取

其次,假设我们已经获取i-1个物品的价值最大值,所有dp[i-1]的值,那么根据状态方程,我们能知道所有dp[i]的值

最后两步联合,整个求解对于任意dp[i][j]成立

  • 实现


 

(编辑:南通站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    热点阅读