查找最小数量的子集的算法，其中每个集合的总和不超过最大值

Question

给定一个正整数数组，找出子集的最小数目，其中:

1. 子集中每个元素的总和不超过一个值，k。
2. 数组中的每个元素在任何子集中只使用一次
3. 数组中的所有值都必须出现在任何子集中。

基本上，一个“填充”算法，但需要最小化容器，并需要确保所有东西都被填满。我目前的想法是按降序排序，当总和超过k时开始创建集合，开始下一个，但不确定什么是更好的方法。

编辑：

Ex：

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都被使用，并且在集合中仅使用一次。希望这能解决问题。

Answer 1

可能有一种更聪明的方法来找到最小数量的集合，但这里有一些代码使用Knuth的算法X来进行精确的覆盖操作，还有一个我去年编写的函数来生成总和小于给定值的子集。我的测试代码首先为问题中给出的数据找到一个解决方案，然后为一个更大的随机列表找到一个解决方案。它几乎可以立即找到最大和为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