求一个算法：比如给定一个80,给定三个数：25、20、15计算如何由三个数得出80,80=2*25+2*15.也就是由2,0,2组成.有什么好的算法吗?

Question

求一个算法：比如给定一个80,给定三个数：25、20、15计算如何由三个数得出80,80=2*25+2*15.也就是由2,0,2组成.
有什么好的算法吗?

Answer 1

我想到的一种算法是类似于广搜,起点是0（available,置为true值）,终点是给定的数,每个数都是一个节点（我猜数据类型应该都是整形）,开始都是unavailable(置为false值),每次扫描都在已有的available的n个节点基础上,加减给出的三个数,创造出6*n个新的available节点(当然会有很多重复的)直到终点available,但是缺点是1、对一些数据可能不好确定搜索终点,2、时间复杂度O(N2),
另外我想到的一个想法是用被求数与已知数的各种组合相加值取模,直到模为零或者存在消不掉的余数,但程序如何实现我还想不到.