具有最小数目的群的最大值

Question

我正在为一个RPG创建一个宏，在Lua中，在它中，我需要用一堆数据来获得最多的集合。要形成一个组，数据必须加到每个组的最小值，并且可能超过这个最小值。

例：1, 2, 4, 5, 5, 6, 7, 10 w/ min = 10将是：6+4, 5+5, 7+1+2, 10。

我将每个骰子的结果分组到一个数组中，并提取可以单独组成组的数据：

for i=#dice, 1, -1 do
    table.sort(dice);
    minimo = tonumber(minimum)
    if dice[i] >= minimum then
        stack.Total = stack.total+1;
        table.insert(stack.dice, 1, math.floor(dice[i]))

        table.remove(dice, i);
    end;
end;

它不一定在Lua，只是一些数学公式会有很大帮助

Answer 1

这里有一个高效的递归解决方案。它很可能没有解决混合整数程序的效果好，但它很简单，不需要外部库。你可能会更快的回忆录它，而牺牲了大量的记忆。

其核心思想是:形成所有可能的满足最小值的组；对于每个这样的组，从剩余的滚动中获得最大的组数；采取最好的解决方案。剩下的就是优化。

第一个优化是只循环一些组。既然我们可以把每一卷都放在一组里，那么最大的一卷是在某个组里。若要避免遍历组的所有排列，请仅列举该组的可能性。

第二种优化方法是，如果找到一个可证明的最优解，就停止搜索。显然，我们不能比最小和的下限更多的组。如果我们制造了这么多，我们就无法提高。

第三个优化是避免枚举重复组。当我们减少i时，我们考虑的是在那个位置不包含元素的组。为了避免重复，我们跳过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)