给定一个正整数数组,求最小子集数,其中:
基本上,一个'填充'算法,但需要尽量减少容器,并需要确保一切得到填补。我目前的想法是按降序排序,当总和超过k时开始创建集合,开始下一个集合,但不确定哪种方法更好。你知道吗
编辑:
例如:
Inputs: arr = [1,2,3,4,5], k= 10
Output: [[1,4,5], [2,3]]
# Other solutions such as [[2,3,4],[1,5]] are also acceptable
# But the important thing is the number of sets returned is 2
在输出集合中,所有1-5都被使用,并且在集合中只使用一次。希望这能解决问题。你知道吗
也许有一种更聪明的方法可以找到集合的最小数目,但是这里有一些代码使用Knuth的算法X来做精确的覆盖运算,还有一个我去年写的函数来生成总和小于给定值的子集。我的测试代码首先为问题中给出的数据找到一个解决方案,然后为一个更大的随机列表找到一个解决方案。它几乎可以立即找到最大和为10的[1,2,3,4,5]的解决方案,但在我以前的32位2GHz机器上解决更大的问题几乎需要20秒。你知道吗
这段代码只打印一个最小大小的解决方案,但是修改它以打印所有最小大小的解决方案并不困难。你知道吗
输出
相关问题 更多 >
编程相关推荐