比如从 1,2,5,6,8 里边凑出 7 和 9 两位数。 前边的数不能重复使用,需要找出最优凑法。 有木有大佬提供下思路
1
minami 2021-07-19 17:42:36 +08:00
不理解凑数是什么意思,就简单理解成加法吧,用 BFS 就可以了
|
2
misdake 2021-07-19 18:00:57 +08:00
凑是指从数的集合中(不放回地)挑选一些数相加得到目标数么?
最优凑法里的最优是指什么最优? 问题里每个数字有三种可能状态,不使用、拿去凑 7 、拿去凑 9,要求所有凑 7 的数加一起是 7,所有凑 9 的数字加一起是 9 。 我的话会考虑用记忆化搜索,搜索空间是[使用前 n 个数字][凑 7 还差多少][凑 9 还差多少],从[5][7][9]开始。找到[任意][0][0]就是一个解。 |
3
xupefei 2021-07-19 18:26:00 +08:00 via iPhone
简化版背包问题
|
4
xupefei 2021-07-19 18:26:49 +08:00 via iPhone
只能填表,没有捷径
|
5
threebr 2021-07-19 18:32:12 +08:00
可以用简单的深度搜索算法,递归深度为 m×n 。m 是[1,2,5,6,8 ]的长度,n 是[7,9]的长度。
|