最小数值中的最大组数

下面是一个有效的递归解决方案。它可能不如解决混合整数规划问题的方案那么可扩展，但它简单，不需要外部库。你可能可以通过记忆化来使它更快，但代价是很多内存。

核心思想是：形成所有满足最低限度的可能组合；对于每个这样的组，使用剩余的掷骰子最大化组数；选择最佳解决方案。其余的是优化。

第一个优化是仅循环一些组。因为我们可能会将每个骰子都放入一个组中，所以最大的骰子就在某个组中。为了避免循环所有组的排列，仅枚举那个组的可能性。

第二个优化是在找到可证明的最佳解后停止搜索。很明显，我们不能使组数多于最低限度总和的底部。如果我们达到了这个数字，就不能再进一步提高。

第三个优化是避免枚举重复的组。当我们减少“i”时，我们考虑的组不包括该位置的元素。为避免重复，我们跳过与我们刚刚拒绝的元素相同的元素。

在Python 3中：

def all_groups(minimum, rolls, j):
    roll = rolls[j]
    if minimum <= roll:
        yield [roll], rolls[:j]
    else:
        i = j - 1
        while i >= 0:
            for group, rest in all_groups(minimum - roll, rolls, i):
                group.append(roll)
                rest.extend(rolls[i + 1 : j])
                yield group, rest
            while i > 0 and rolls[i - 1] == rolls[i]:
                i -= 1
            i -= 1

def max_groups_helper(minimum, rolls, lower_bound=0):
    upper_bound = sum(min(roll, minimum) for roll in rolls) // minimum
    if upper_bound < lower_bound:
        return None
    if upper_bound <= 0:
        return []
    best = []
    for group, rest in sorted(
        all_groups(minimum, rolls, len(rolls) - 1),
        key=lambda group_rest: sum(group_rest[0]),
    ):
        candidate = max_groups_helper(minimum, rest, max(lower_bound - 1, len(best)))
        if candidate is None:
            continue
        candidate.append(group)
        best = candidate
        if len(best) >= upper_bound:
            break
    return best

def max_groups(minimum, rolls):
    assert minimum > 0
    rolls = list(rolls)
    return max_groups_helper(minimum, rolls, 0)