【编程之美】最短路径

最短路径

任意给定两个数字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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

UOJ#179. 线性规划(线性规划)

有 nn 个实数变量 x1,x2,…,xnx1,x2,…,xn 和 mm 条约束,其中第 ii 条约束形如 ∑nj=1aijxj≤bi∑j=1naijxj≤bi...

8230
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (中)

上一部分提到了节点(Node),代价(Cost),估价公式等基本概念,有了这些知识铺垫 就可以正式开启寻路之旅了! ? 如上图,这是一个5行8列的网格,黄色节点...

26660
来自专栏数据结构与算法

P2280 [HNOI2003]激光炸弹

题目描述 ? 输入输出格式 输入格式: 输入文件名为input.txt 输入文件的第一行为正整数n和正整数R,接下来的n行每行有3个正整数,分别表示 输...

32950
来自专栏WD学习记录

牛客网 和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100...

17810
来自专栏calmound

hust Dating With Girls

http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=573#problem/B 题意:求最大权...

29340
来自专栏深度学习那些事儿

pytorch中autograd以及hook函数详解

有些公式为图片,如果这个页面加载不出来,请看这里:https://oldpan.me/archives/pytorch-autograd-hook

1.6K100
来自专栏软件开发 -- 分享 互助 成长

C++中巧妙的位运算

位运算要多想到与预算和异或运算,并常常将两个数对应位上相同和不同分开处理 一、x&(x-1)消除x二进制中最右边的一个1。 这个比较厉害,比如统计某个 二、与和...

35960
来自专栏小二的折腾日记

LeetCode-52-N-Queens-II

只返回N皇后问题结果的种数。 因此不需要每一个字符串置位了,只需要判断一个位置的横竖,斜45度和斜135度方向的值即可。依然采用递归的方式,这里需要注意的是,由...

6110
来自专栏鸿的学习笔记

写给开发者的机器学习指南(十)

An attempt at rank prediction for topselling books using text regression

9730
来自专栏Java3y

Map集合、散列表、红黑树介绍

20030

扫码关注云+社区

领取腾讯云代金券