专栏首页程序员互动联盟【编程之美】最短路径

【编程之美】最短路径

最短路径

任意给定两个数字A和B,通过将A和6个数(7,-7,5,-5,12,-12)做加减运算,运算次数不限,每个数可以被使用多次,求从A到B最少要经过多少次运算?

比如:A=0, B=19,从A到B的一条路径为{0,7,19},经过2次运算得到。{0, 5, 12,19}也是符合要求的一条路径,但是需要经过3次运算才可以得到。所以最少要经过2次运算才可以实现从0到19.

01

class

解题思路:

方案一:DP从A到B,可以简化为从0到abs(A-B)

设S[i]为从0到i的最短路径

那么 S[i]=min(S[v]+S[i-v])

方案二:限制条件: det=12a+7b+5c

目标函数: S=|a|+|b|+|c|

a,b,c若有一个以上为0,则变成二元整数线性规划的问题,好像是经典问题,易解。

如果三者都不为零,则:

如果b,c同号,则一个(7+5)用一个12代替,可以得到更优解

如果b,c异号,则其中必有一个与a异号,(12-7)用5代替,或(12-5)用7代替,可以得到更优解

综上,最优解中,a,b,c肯定至少有一个为0

所以分别做3次二元线性规划,取最优的即可

方案三:题意中的12,-12完全没意义,因为可以用(7,5) (-7,-5)代替。

因此只需要考虑(7,-7,5,-5)。

A + (7x+5y) = B  -> 7x+5y=(B-A)

ax+by=d

然后扩展欧几里得算法。

code也是一种艺术,它能展现出自己的美。

本文分享自微信公众号 - 程序员互动联盟(coder_online)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-01-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如果94年柳传志听了倪光南的话走向技工贸路线,那现在联想是电脑界的大咖还是倒闭?

    最近一段时间柳传志退休的时间在网络上炒的比较厉害,之前一直炒的比较厉害的杨元庆竟然不是接任者,由于大家都拿华为公司来对比联想,所以杨元庆更是一度被民众拿来作为调...

    程序员互动联盟
  • 10年前的顶配电脑放到现在是什么水平?

    很有意思的一个话题,说说自己亲身体验,10年前配的第一台电脑还是在中国村大厦那个时代电脑攒机在当时还算是一项技术含量非常大的技术,难点不在于各种配置的组合主要还...

    程序员互动联盟
  • 一个Java程序员的年终总结

    新的一年过去了,又到了该总结的时候。这一年可以说是很重要一年,很多事情,都阶段性的开花结果。 先是2月份,去了海辉,实在说,没有进去这前想的那么...

    程序员互动联盟
  • 费马小定理证明

      任意取一个质数,比如13。考虑从1到12的一系列整数1,2,3,4,5,6,7,8,9,10,11,12,给这些数都乘上一个与13互质的数,比如3,得到3,...

    饶文津
  • 2,StructuredStreaming的事件时间和窗口操作

    Spark学习技巧
  • Spark Structured Streaming + Kafka使用笔记

    这篇博客将会记录Structured Streaming + Kafka的一些基本使用(Java 版)

    大鹅
  • 12年程序员职业生涯得到的12个经验教训

    12年程序员职业生涯得到的12个经验教训 我已经在ThoughtWorks工作了12年。是不是有点不可思议?回首我的职业生涯,我想写一写我在这些年中经历的困难,...

    用户1289394
  • 多台filebeat+ELK模拟记录 原

    基于 《filebeat+logstash配置搭建 》同一台及其做ELKF,现在做多台filebeat的实践。

    用户1409099
  • 互联网行业法律动态报告(2014年12月)

    互联网行业法律动态报告(2014年12月) 腾讯互联网法律研究中心 重点摘要: 2014年12月,网络治理、网络犯罪、知识产权、竞争规则、电子商务...

    腾讯研究院
  • AkShare-股票数据-交易日历

    更新 股票-交易日历 接口,之前一直没有发现合适的股票-交易日历数据,最近发现新浪财经提供了本数据,特提供本接口可以获取股票从 1990-12-19 到 202...

    AkShare

扫码关注云+社区

领取腾讯云代金券