动态规划(DP)之闫式分析法

这篇具有很好参考价值的文章主要介绍了动态规划(DP)之闫式分析法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划(DP):是运筹学的一个分支,是求解决策过程最优化的过程

适用场景:用于求解具有某种最优性质的问题

闫式分析法基本思想:将待求解问题分解成若干个子问题,求解子问题的数学关系式,然后从这些子问题的关系式拼接成原问题的解法,然后将问题的条件从低到题目条件分层计算,需要注意的是经过分层得到的答案往往不是互相独立的,保存已解决的低层答案,在计算下一层或高层数据结果时再找出已求得的答案用以避免大量的重复计算,节省时间

优化方向:DP的所有优化都是对代码的等形变换,它和题目无关,和代码的逻辑有关

代码编写:使用DP应该是使用循环,将运算过程逐渐算出,即层次计算,先计算出底层的数据然后存储,在计算高层数据时再调用所需存储的计算结果,来达到避免重复计算

子问题分解关系式限制:

  1. 不重复
  2. 不遗漏

闫式分析法解题步骤:将DP问题中的重要信息提取出来,将题目化成状态表示状态计算,而状态表示又分为集合属性,以经典的01背包问题来举例,如下图:

动态规划(DP)之闫式分析法,数据结构与算法,动态规划,算法

在01背包问题中一共有2^n次方个方案,而求的是其价值最大的方案,在只考虑前i个物品时,分为考虑第 i 个物品和不考虑第 i 个物品,也就是将一个大问题分为了两个子问题。

动态规划(DP)之闫式分析法,数据结构与算法,动态规划,算法

将两个子问题求解:在求解考虑第i个物品时,需确定背包剩余容量是否能装下第 i 个物品

问题 代码表示
考虑第 i 个物品 f ( i-1,j )
不考虑第 i 个物品 f ( i-1,j - v[ i ]) + w[ i ]
代码(暴力):01背包问题(一般写法)
#include<iostream>
#include<algorithm>
using namespace std;
//题目所定义的物品最大数
const int N = 1010;
//输入的物品数n、背包容量m
int n,m;
//存储物品的体积、价值
int v[N],w[N];
//二维数组解
int f[N][N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++){
        cin >> v[i] >> w[i];
    }
    
    //循环的是物品数,表示的是考虑前i个物品
    for(int i = 1 ; i <= n ; i++){
        //循环的是背包容量,表示的是考虑背包还有j个容量
        for(int j = 0; j <= m ; j++){
            //左半边子集,即不选取这个物品,保持上层结果
            f[i][j] = f[i-1][j];
            
            //背包剩余容量能够装下第i个物品
            if(j >= v[i]){
                //右半边子集,即当价值大于上层结果,更新集合
                f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]);
            }
            
        }
    }
    
    cout << f[n][m] <<endl;
    return 0;
}

总结:以物品数为外层循环来循环容量,即对物品从第一个到最后一个都是进行选与不选操作,通过增加物品,来逐层计算,每层计算都只需调用上一层的计算结果来进行简单计算,避免了底层数据多次计算

代码(优化):01背包问题(优化空间写法)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
//将原本二维数组优化成了一维数组
int f[N];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    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]);
        }
    cout << f[m] << endl;
    return 0;
}

总结:

优化一:将原本的二维数组优化为了一维数组,其思想是滚动数组,通过在 i-1 层向 i 层更新的时候,数组逐下从小到大覆盖数据,但数据的计算是下标从大到小进行计算的,这样在计算高层时可以保证数据时低层的

优化二:由于是一维数组,所以原本左边子问题的关系式可直接省略,因为 f[i][j] = f[i-1][j]; 等式的作用就是等价于原值,所以不进行覆盖即可文章来源地址https://www.toymoban.com/news/detail-840403.html

到了这里,关于动态规划(DP)之闫式分析法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 层次分析法(MATLAB)

    对之前的学习进行总结,整个比赛下来好像就用到了这个方法,最后也不知道对不对,反正最后还有点赶,就是很懵的那种,对于层次分析话的还是有点了解了,由于是纯小白,有错误的地方希望各位大佬能够指出。 目录 数据提取 归一化处理 判断矩阵 一致性检验  算术平

    2024年02月12日
    浏览(44)
  • 层次分析法

    人们常常面临一个由 相互关联、相互制约 的众 多因素 构成的复杂而往往 缺少定量数据 的系统; AHP是对一些较为复杂、较为模糊的问题作出决策的简易方法,特别适用于那些难于完全定量分析的问题; 美国运筹学家T. L. Saaty 教授于上世纪70 年代初期提出的一种简便、灵活

    2024年02月02日
    浏览(63)
  • 【爬虫逆向分析实战】某笔登录算法分析——本地替换分析法

    作者最近在做一个 收集粉币 的项目,可以用来干嘛这里就不展开了😁,需要进行登录换算token从而达到监控收集的作用,手机抓包发现他是通过APP进行计算之后再请求接口的,通过官网分析可能要比 APP逆向方便多 ,但是通过这几天的观察我并没有头绪,这篇文章草稿创建了

    2024年02月05日
    浏览(47)
  • 数学建模:层次分析法

    🔆 文章首发于我的个人博客:欢迎大佬们来逛逛 将问题条理化,层次化,构建出一个有层次的结构模型。层次分为三类: 目标层,准则(指标)层,方案层 。 比较指标层中不同指标之间的相对重要程度,并且构建一个 成对比较矩阵 。 自行判断两个不同指标的相对重要程

    2024年02月10日
    浏览(45)
  • 数学建模——层次分析法

    正互反矩阵:若矩阵中每个元素a(ij)0且满足a(ij)*a(ji)=1。 层次分析法中,我们构造的判断矩阵均是正互反矩阵。 一致矩阵:若正互反矩阵满足a(ij)*a(jk)=a(ik)。 一致矩阵的秩为1。 一致矩阵有一个特征值为n,其余特征值均为0。 判断矩阵越不一致时,最大特征值与n相差越大。 一

    2024年02月16日
    浏览(40)
  • 层次分析法(matlab实现)

           在决策理论中,层次分析法是一种以 数学 和 心理学 为基础,组织和分析复杂决策的结构化技术,它代表了一种 量化决策标准权重 的准确方法,通过成对比较,利用个别专家的经验来估计因素的相对大小        在很多情况下,我们对事物的评价,应该多维度的进

    2024年02月09日
    浏览(43)
  • 线性判别分析法(LDA)

            在主成分分析法(PCA)中,我们对降维算法PCA做了总结。这里我们就对另外一种经典的降维方法线性判别分析(Linear Discriminant Analysis, 以下简称LDA)做一个总结。LDA在模式识别领域(比如人脸识别,舰艇识别等图形图像识别领域)中有非常广泛的应用,因此我们有

    2023年04月08日
    浏览(39)
  • 【自控笔记】线性系统时域分析法

    二阶系统单位阶跃

    2024年04月11日
    浏览(42)
  • 数学建模:主成分分析法

    🔆 文章首发于我的个人博客:欢迎大佬们来逛逛 构建原始数据矩阵 X X X ,其中矩阵的形状为 x ∗ n x * n x ∗ n ,有 m m m 个对象, n n n 个评价指标。 然后进行矩阵的 归一化处理 。 首先计算矩阵的指标之间的 相关系数矩阵 R R R 。使用matlab 的 corr 即可得到。 计算相关系数矩

    2024年02月10日
    浏览(52)
  • 功能测试—边界值分析法

    边界值分析法就是对输入的边界值进行测试的一种黑盒测试方法。通常边界值分析法是作为对等价类划分法的补充,这种情况下,其测试用例来自等价类的边界 1 为什么引入边界值分析法? 测试实践表明,大量的故障往往发生在输入定义域的边界上,而不是在其内部。因此,

    2024年02月09日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包