给定一个正整数数组，找到最小子集数，其中:
- 子集中每个元素的总和不超过一个值k。
- 数组中的每个元素在任何子集中只使用一次
- 数组中的所有值都必须出现在任何子集中。
基本上，一个“填充”算法，但需要最小化容器并需要确保所有内容都被填充。我目前的想法是按降序排序并在总和超过 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 来执行精确覆盖操作，以及我去年编写的一个函数来生成总和小于 a 的子集给定的值(value)。我的测试代码首先为问题中给出的数据找到解决方案，然后为更大的随机列表找到解决方案。它几乎立即找到了最大和为 10 的 [1, 2, 3, 4, 5] 的解决方案，但在我的旧 32 位 2GHz 机器上需要将近 20 秒才能解决更大的问题。
此代码仅打印一个最小尺寸的解决方案，但不难修改它以打印所有最小尺寸的解决方案。
""" Find the minimal number of subsets of a set of integers
which conform to these constraints:
The sum of each subset does not exceed a value, k.
Each element from the full set is only used once in any of the subsets.
All values from the full set must be present in some subset.
See https://stackoverflow.com/q/50066757/4014959
Uses Knuth's Algorithm X for the exact cover problem,
using dicts instead of doubly linked circular lists.
Written by Ali Assaf
From http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
and http://www.cs.mcgill.ca/~aassaf9/python/sudoku.txt
Written by PM 2Ring 2018.04.28
"""
from itertools import product
from random import seed, sample
from operator import itemgetter
#Algorithm X functions
def solve(X, Y, solution):
if X:
c = min(X, key=lambda c: len(X[c]))
for r in list(X[c]):
solution.append(r)
cols = select(X, Y, r)
yield from solve(X, Y, solution)
deselect(X, Y, r, cols)
solution.pop()
else:
yield list(solution)
def select(X, Y, r):
cols = []
for j in Y[r]:
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].remove(i)
cols.append(X.pop(j))
return cols
def deselect(X, Y, r, cols):
for j in reversed(Y[r]):
X[j] = cols.pop()
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].add(i)
#Invert subset collection
def exact_cover(X, Y):
newX = {j: set() for j in X}
for i, row in Y.items():
for j in row:
newX[j].add(i)
return newX
#----------------------------------------------------------------------
def subset_sums(seq, goal):
totkey = itemgetter(1)
# Store each subset as a (sequence, sum) tuple
subsets = [([], 0)]
for x in seq:
subgoal = goal - x
temp = []
for subseq, subtot in subsets:
if subtot <= subgoal:
temp.append((subseq + [x], subtot + x))
else:
break
subsets.extend(temp)
subsets.sort(key=totkey)
for subseq, _ in subsets:
yield tuple(subseq)
#----------------------------------------------------------------------
# Tests
nums = [1, 2, 3, 4, 5]
k = 10
print("Numbers:", nums, "k:", k)
Y = {u: u for u in subset_sums(nums, k)}
X = exact_cover(nums, Y)
minset = min(solve(X, Y, []), key=len)
print("Minimal:", minset, len(minset))
# Now test with a larger list of random data
seed(42)
hi = 20
k = 2 * hi
size = 10
nums = sorted(sample(range(1, hi+1), size))
print("\nNumbers:", nums, "k:", k)
Y = {u: u for u in subset_sums(nums, k)}
X = exact_cover(nums, Y)
minset = min(solve(X, Y, []), key=len)
print("Minimal:", minset, len(minset))
输出
Numbers: [1, 2, 3, 4, 5] k: 10
Minimal: [(2, 3, 5), (1, 4)] 2
Numbers: [1, 2, 3, 4, 8, 9, 11, 12, 17, 18] k: 40
Minimal: [(1, 8, 9, 18), (4, 11, 17), (2, 3, 12)] 3
关于python - 找到每个集合的总和不超过最大值的最小子集数的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50066757/