首页 > 其他分享 >动态规划DP

动态规划DP

时间:2023-02-04 17:13:20浏览次数:52  
标签:状态 那么 转移 物品 动态 规划 我们 DP

动态规划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]\)的和,那么不难得出状态转移方程:

    \[f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j] \]

  • 背包DP

    • 01背包

      对于\(m\)个物品,都有着对应的代价\(w[i]\)和价值\(v[i]\),我们可以消耗代价获得对应的价值,且每个物品的价值只能被获得一次,求消耗不超过\(t\)的代价所能获得的最大价值。
      那么,我们有\(dp[i][j]\)描述只考虑前\(i\)个物品且剩余总代价为\(j\)时,所获得的价值最大值
      显然,对于一个物品,我们只有两种选择,买与不买,那么我们显然要在这两种情况之间选一个最大值转移到下一个状态

      1. 对于不买此物品

        总价值等于只考虑到上一个物品的最大价值,即\(f[i - 1][j]\)
      2. 对于买此物品

        我们的剩余总代价减少了,但与此同时我们获得了此物品的价值,总价值为\(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]);

标签:状态,那么,转移,物品,动态,规划,我们,DP
From: https://www.cnblogs.com/Kazdale/p/17091838.html

相关文章

  • 人生规划
    1,考研有用,但最好大学毕业就考,最多给自己两次机会。2,珍惜应届生身份,第一份工作不要随意签。一般来说公务员>人才引进>国企>外资>民企,但排序也可能随时代而变化。3,实在进不......
  • 2023网络爬虫 -- 获取动态加载数据
    1、爬取的网址http://www.kfc.com.cn/kfccda/storelist/index.aspx2、要爬取的内容,输入关键字,点击查询,获取餐厅名称和餐厅地址3、F12,打开开发者工具,点击查询,抓包4、点......
  • 如何根据自身条件进行软件测试的职业规划
    关于职业的规划可以分为三个阶段,分别是:初级测试工程师,高级测试工程师,测试开发/测试主管。这里说明一下,之前的两个阶段都是一致的,都是对于软件测试技能的积累。当完成最......
  • P1472 奶牛家谱 Cow Pedigrees(DP)
    题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3<=N<200)......
  • 缩点-将图转化为 DAG 跑 DP :P1455,P2169
    之前有提到,缩点可以将一张有向图转化为一张有向无环图(DAG),这样我们就可以在图上跑DP了。而我们实现DP的手段一般是在拓扑排序中实现,有时候也会用到最短路。P1455https......
  • Error: client: etcd cluster is unavailable or misconfigured; error #0: client:
    这种报错是因为配置出现了问题我们需要修改etcd的配置文件就可以了vim/etc/etcd/etcd.conf  重启etcd即可systemctlrestartetcd.service ......
  • 数位DP
    数位DPTODO补充数位$DP$概念等补充题目分析及过程增加题目题目CF1073E.SegmentSumCF1073E.SegmentSum求$L\simR$之间最多不包含$K$个数码的数的和......
  • 动态规划(一)
    1.贪心贪心能解的题,搜索也可以解贪心只是提高的效率,不保证正确性860.柠檬水找零(贪心模板)在柠檬水摊上,每一杯柠檬水的售价为5美元。顾客排队购买你的产品,(按账单......
  • 动态规划及优化
    决策单调性定义:单调矩阵:每行最值位置单调不降。完全单调矩阵:每个子矩阵都是单调矩阵,这里的子矩阵可以不连续。蒙日矩阵:满足四边形不等式的矩阵,蒙日矩阵一定是完全单调......
  • Vue使用:style动态给css中某样式赋值
    template中<spanclass="successOrError":style="{'--fontColor':"green"}">成功</span>css中<stylelang="scss"scoped>.successOrError{font-size:14px;......