Algorithm for optimal partition of a multiset with bounded sum.

Question

Consider the following problem:

Let $S$ be a multiset (you can think of it as an array) of positive integers. Given a bound $W\geq \max(S)$, we want to find a partition of $S$ into multisets $\{S_1,...,S_k\}$ such that $\sum S_i \leq W$ for all $i\in\{1,...,k\}$ and $k$ is as small as possible.

For example if $S=\{1, 3, 4, 2, 1, 5, 3\}$ and $W = 5$, an answer would be $\{\{5\}, \{1, 4\}, \{3, 2\}, \{3, 1\}\}$ or $\{\{5\}, \{4\}, \{3, 2\}, \{3, 1, 1\}\}$.

My attempt for solving it was using a greedy approach: we can sort the array and then try to construct multisets from the extremes, in our example, $S=\{1, 3, 4, 2, 1, 5, 3\}$ would become $S=\{1, 1, 2, 3, 3, 4, 5\}$, so we start on the right, as $W=5$, there's nothing to do, so now we have $\{1, 1, 2, 3, 3, 4\}$, starting from the right we have $4<5$, so we try on the left, as $4+1=5$ we are done. Now we have $\{1, 2, 3, 3\}$, so we try with $3$ and then $1$, as $3+1=4<5$ we go for the next, but $2$ won't do, so we stop and are left with $\{2, 3\}$, going one last time we see that this is a valid multiset and we are done. Here's a Python function that (hopefully) does what I though:

def get_partition(input_list: list, bound: int) -> list:
    ret = []
    sorted = input_list[:]
    sorted.sort()
    while sorted:
        temp = []
        temp.append(sorted.pop())
        if sum(temp) == bound:
            ret.append(temp[:])
        else:
            for index in range(len(sorted)):
                temp.append(sorted.pop(0))
                if sum(temp) == bound:
                    ret.append(temp[:])
                    break
                elif sum(temp) > bound:
                    sorted = [temp.pop()]+sorted
                    ret.append(temp[:])
                    break
    return ret

I'm almost certain that this approach gives a sub-optimal solution in general, but at least doesn't seem too bad. I'd like to know if an optimal algorithm for this problem can be feasible, because this looks like some generalization for the Partition Problem, which is $NP$-Complete, so there may be no hope for it.

Answer 1

This is the bin packing problem, which is NP-hard, and the corresponding decision problem is NP-complete. Your greedy algorithm is known as first-fit decreasing, and tight bounds are known for the approximation ratio.

Answer 2

This problem reminded me of the well-known coin change problem. Can be solved easily by using Dynamic Programming. Click here for more information. Maybe some variation of it to split the set into subsets.