求一个凑数算法

2021 年 7 月 19 日
 starlz

比如从 1,2,5,6,8 里边凑出 7 和 9 两位数。 前边的数不能重复使用,需要找出最优凑法。 有木有大佬提供下思路

1773 次点击
所在节点    算法
5 条回复
minami
2021 年 7 月 19 日
不理解凑数是什么意思,就简单理解成加法吧,用 BFS 就可以了
misdake
2021 年 7 月 19 日
凑是指从数的集合中(不放回地)挑选一些数相加得到目标数么?
最优凑法里的最优是指什么最优?

问题里每个数字有三种可能状态,不使用、拿去凑 7 、拿去凑 9,要求所有凑 7 的数加一起是 7,所有凑 9 的数字加一起是 9 。
我的话会考虑用记忆化搜索,搜索空间是[使用前 n 个数字][凑 7 还差多少][凑 9 还差多少],从[5][7][9]开始。找到[任意][0][0]就是一个解。
xupefei
2021 年 7 月 19 日
简化版背包问题
xupefei
2021 年 7 月 19 日
只能填表,没有捷径
threebr
2021 年 7 月 19 日
可以用简单的深度搜索算法,递归深度为 m×n 。m 是[1,2,5,6,8 ]的长度,n 是[7,9]的长度。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://study.congcong.us/t/790435

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX