Maximum of groups with minimum numbers

user_15457253 0
Viewed 97

I'm creating a macro for an RPG, in Lua, in it I need to get the most sets with a stack of dices. to form a group the data must add up to the minimum of each group, and may exceed this minimum.

ex: 1, 2, 4, 5, 5, 6, 7, 10 w/ min = 10 will be: 6+4, 5+5, 7+1+2, 10.

I grouped the result of each dice into an array, and pulled out the data that can form groups on their own:

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;

it doesn't have to be in Lua, just some mathematical formula will be of great help

math lua algorithm
1 Answers

Here's an efficient recursive solution. It likely doesn't scale as well as solving a mixed integer program would, but it's simple and doesn't require an external library. You could probably make it even faster by memoizing it, at the expense of a lot of memory.

The core idea is: form all possible groups that meet the minimum; for each such group, make the max number of groups out of the remaining rolls; take the best solution. The rest is optimization.

The first optimization is to loop over only some groups. Since we might as well put every roll in a group, the largest roll is in some group. To avoid looping over all permutations of the groups, enumerate the possibilities for that group only.

The second optimization is to stop searching if we find a provable optimum. Obviously we can't make more groups than the floor of the sum over the minimum. If we make this many, we can't improve.

The third optimization is to avoid enumerating duplicate groups. When we decrease i, we're considering groups that did not include the element at that position. To avoid duplicates, we skip i over the elements identical to the one that we just rejected.

In 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)
user_21446690
Related