初始160，单次只能+50；-60或-140，如何在最短步骤归0？ - 数学吧

level 3

古拉德123 楼主

初始160，单次只能+50；-60或-140，如何在最短步骤归0？
不能为负，例如90的时候，必须先+50，再-140，不能先-140，再+50
此类问题是否有较为简单的算法方案？

2024年05月17日 07点05分 1

level 11

贴吧用户_0PMyKbe

如果步骤不多，可以试试迭代深搜

2024年05月17日 07点05分 2

level 7

原来可以辣么帅

对50取余即可，应该是5步，两个50，两个-60，一个-140

2024年05月17日 09点05分 4

level 1

忘了，不知道，别问我

感觉为负影响不大吧，因为中途为负的情况可以把顺序调换一下就不出现中途为负了

2024年05月17日 09点05分 5

level 9

FMaj6

由于5和6互素，所以只要输入是10的倍数都有解。这类问题最快的算法是枚举10到270的全部结果，存成一个表，(270不一定是上界不过懒得算了，实际操作中选最大的那个第一步不是-140的数)输入在10到270之间的话就直接查表出结果，输入超过范围就模280，然后查表出结果。

2024年05月17日 09点05分 6

level 13

AlphB

顺序无所谓，所以可以忽视不能为负的条件。
动态规划，记160回到原点需要的步数为dp(160)
那么dp(160)=min{dp(210), dp(100), dp(20)}+1，然后写个Map记录已经算出来的步数作为缓存。要用广度优先搜索，不然会跑到正负无穷去

2024年05月17日 09点05分 7

level 15

ybluebaby

楼上说得对，5步就行。

2024年05月17日 09点05分 8

level 13

AlphB

也可以当迭代到超过 ±lcp(50, 60, 140)=2100时候，直接return一个2^31-1，从而保证不采用这个数

2024年05月17日 09点05分 9

level 13

AlphB

还是广搜好，保证找到最优路径时立刻结束

2024年05月17日 09点05分 10

FMaj6

Θ(n)不嫌慢吗，直接打表0-270，模280后查表就行 [阴险]

2024年05月17日 09点05分

AlphB

@FMaj6 看清题目楼主问的是“这类”问题，所以数据不一定是给的数据 [滑稽]

2024年05月17日 09点05分

level 9

FMaj6

典型的用很少的空间就能把时间从Θ(n)变成Θ(1)的问题，实际操作中如果需要反复调用肯定用我的方法

2024年05月17日 09点05分 11

level 13

能登麻美子💍

线性规划就能做顺序不影响所以非负约束没意义

2024年05月17日 10点05分 12