首页 > 其他分享 >mod4最优路径问题

mod4最优路径问题

时间:2023-05-31 23:36:54浏览次数:25  
标签:mod4 路径 最小 问题 余数 最优


mod4最优路径问题


如下图:

  

mod4最优路径问题_最优路径


从1到4找出一条路径,要求路径的总长度mod4的余数最小。


分析:一条从1到4的最优路径,在它走到2或3时mod4的余数不一定最小。也就是说,最优策略的子策略不一定最优,所以本问题不满足最优化原理,那么也就不能用动态规划来解决。但是我们可以把它转化为判定性问题,用递推来解决。


设dp[k][i]为bool型数组,表示从1点到k点长度mod4为i的路径是否存在,设len[k][i]表示从第k-1到第k点之间的第i条边的长度。那么就有


   

mod4最优路径问题_递推_02


显然边界条件是:

    

mod4最优路径问题_数组_03

那么结果就是使

mod4最优路径问题_数组_04

为真的最小的i的值。




标签:mod4,路径,最小,问题,余数,最优
From: https://blog.51cto.com/u_16146153/6391038

相关文章

  • Bellman-Ford算法——为什么要循环n-1次?图有n个点,又不能有回路,所以最短路径最多n-1边
    单源最短路径给定一个图,和一个源顶点src,找到从src到其它所有所有顶点的最短路径,图中可能含有负权值的边。Dijksra的算法是一个贪婪算法,时间复杂度是O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在有负权值边的图中不适用,Bellman-Ford适合这样的图。在网络路由中,该算法会被用作距......
  • bat脚本在C:\Program Files (x86)使用普通权限运行与使用管理员权限运行获取当前路径
    bat脚本在C:\ProgramFiles(x86)使用管理员权限运行获取当前路径不对。bat脚本如下:@echooffset"current_dir=%cd%"echoCurrentdirectory:%current_dir%set"filepath=%current_dir%\1.txt"setlocalenabledelayedexpansionifexist"%filepath%"(......
  • 央企财务共享建设路径四大趋势洞察
    构建世界一流财务管理体系是央企从“大”走向“强大”,甚至“伟大”,从“量变”走向“质变”,发展成为世界一流企业的必由之路。智能财务共享服务的建设又是央企构建世界一流财务管理体系的“加速器”。在央企纷纷实践共享服务的背景下,不难发现央企财务共享服务发展的四大趋势:趋势一:拓......
  • linux获取程序当前所在路径的方法
    直接使用pwd不行,linux系统中有个符号链接:/proc/self/exe 它代表当前程序,我们可以用readlink读取它的源路径就可以获取当前程序的绝对路径。charcurrent_absolute_path[MAX_SIZE];//获取当前程序绝对路径intcnt=readlink("/proc/self/exe",current_absolute_path,MAX_SIZ......
  • spfa任意两点间最短路径
    #include<iostream>#include<queue>#include<string.h>usingnamespacestd;#defineINF0x3f3f3f3f;constintN=3000;intn,m;intg[N][N],dist[N];boolst[N];queue<int>q;voidspfa(intstart){st[start]=true;dist[s......
  • 第五节 3绝对路径和相对路径
    绝对路径:从根目录开始,一直到你需要的文件路径'D:\Python视频\Python9期视频\day09\02绝对路径和相对路径.py'相对路径:从当前文件夹开始,到你需要的文件路径,只需要输入文件路径,要打开的文件必须和运行的py文件必须得在一个文件夹下'02绝对路径和相对路径.py'fr=open......
  • 算法 dfs 二叉树的所有路径
    480. 二叉树的所有路径给一棵二叉树,找出从根节点到叶子节点的所有路径。Example样例1:输入:{1,2,3,#,5}输出:["1->2->5","1->3"]解释:1/\23\5样例2:输入:{1,2}输出:["1->2"]解释:1/2"""DefinitionofTreeNode:classTree......
  • 【无人机三维路径规划】基于蚁群算法实现无人机三维路径规划含Matlab代码
    ⛄内容介绍随着无人机可执行任务的多样化,航迹规划成为其顺利完成任务的基本前提。针对该问题,提出了基于蚁群算法的无人机航迹规划方法。运用等效地形模拟方法,将作战区域中的敌方威胁、地形障碍等效为山峰,构建了无人机航迹规划的场景。以此为基础,采用抽象蚁群,对起始点和终点已知的......
  • linux 中find命令查找到文件仅显示文件名、路径名、完整路径
     001、[root@PC1test3]#lstest1test2[root@PC1test3]#tree##测试数据.├──test1│  └──a.txt└──test2└──b.txt2directories,2files[root@PC1test3]#find./-name"*.txt"##一般显示模式./test1/a.txt......
  • java spring添加自义定拦截器后发生访问路径错误,状态码应该返回404时却返回200的bug
    javaspring添加自义定拦截器后发生访问路径错误,状态码应该返回404时却返回200的bug问题自义定拦截器LoginInterceptor继承HandlerInterceptor,自义定配置类继承WebMvcConfigurer。配置类中@OverridepublicvoidaddInterceptors(InterceptorRegistryregistry){......