python - Grouping values from list into buckets to keep sum of values at or below threshold

Question

I have a list of times in minutes that represent the time it takes to do some job, but the amount of time spent working cannot exceed 240 minutes in any given day.I would like to separate into N groups such that the sum of the items in the group does not exceed the threshold (240 in this example).

An example list could be [60, 70, 90, 120, 180, 240]

One possible solution to the above list would be: [[240], [180, 60], [70, 90], [120]]. Note how each of the sums in each list does not exceed the threshold of 240 while leaving some leftover is fine, but how do I know this is the most optimal solution? Optimal being defined as simultaneously minimizing leftover and the number of buckets.

I've been working on trying to do this with some for loops in Python but it feels about as inefficient as possible. Also, due to the method of removing items from the list, the for loop isn't iterating over all values. Below is my attempt.

import random
import math

def roundup(x):
    return int(math.ceil(x / 10.0)) * 10

threshold = 240;

randomlist = []

for i in range(0,10):
    n = random.randint(30,240)
    randomlist.append(roundup(n))

days = []

print (randomlist)

for item in randomlist:
    schedule = []
    schedule.append(item)
    minutes_remaining = threshold - item
    for item2 in randomlist:
        if randomlist.index(item) != randomlist.index(item2):
            if item2 <= minutes_remaining:
                minutes_remaining -= item2
                schedule.append(item2)
                randomlist.remove(item2)
    randomlist.remove(item)
    days.append(schedule)

print (days)

标签： python

Answer 1

from itertools import permutations, product, accumulate

THRESHOLD = 240


def make_groups(lst, n):
    """
    Make n groups. The sum of the items in the group does not exceed 
    the threshold.
    """
    groups = []
    grps_range = [range(1, len(lst) - n + 2) for _ in range(n)]
    combo = [i for i in product(*grps_range) if sum(i) == len(lst)]
    for c in combo:
        marker = [0] + list(accumulate(c))
        group = [tuple(sorted(lst[i:j])) for i, j in zip(marker, marker[1:])]
        conform = [sum(g) <= THRESHOLD for g in group]
        if all(conform):
            groups.append(tuple(sorted(group)))

    return groups


def ngroups_leftover(entry):
    """
    Returns number of groups and sum of left over times
    """
    ngroups = len(entry)
    leftover = [THRESHOLD - sum(x) for x in entry]
    return ngroups, sum(leftover)


groups = []
l = [60, 70, 90, 120, 180, 240]
perm = permutations(l)
for p in perm:
    for i in range(1, len(p) + 1):
        result = make_groups(p, i)
        groups += result

unique_groups = set(groups)

x = sorted(unique_groups, key=ngroups_leftover)
# There are many solutions which result in the same number of groups
# and left over time. But, the first entry would do.
print(x[0])

Output

((60, 180), (70,), (90, 120), (240,))

All possible combinations:

[((60, 180), (70,), (90, 120), (240,)),
 ((60, 70), (90, 120), (180,), (240,)),
 ((60, 180), (70, 120), (90,), (240,)),
 ((60, 90), (70, 120), (180,), (240,)),
 ((60, 120), (70, 90), (180,), (240,)),
 ((60, 70, 90), (120,), (180,), (240,)),
 ((60, 180), (70, 90), (120,), (240,)),
 ((60, 180), (70,), (90,), (120,), (240,)),
 ((60,), (70, 90), (120,), (180,), (240,)),
 ((60, 70), (90,), (120,), (180,), (240,)),
 ((60,), (70, 120), (90,), (180,), (240,)),
 ((60, 120), (70,), (90,), (180,), (240,)),
 ((60, 90), (70,), (120,), (180,), (240,)),
 ((60,), (70,), (90, 120), (180,), (240,)),
 ((60,), (70,), (90,), (120,), (180,), (240,))]