Multiple knapsacks problem

multiple_knapsacks_problem.py

"""
Knapsacks have weight capacity; items have weight and value.

We want to find the allocation of items which maximizes the total
carried value.
"""

from typing import List, Set, Tuple


def remove_subsets(combinations: List[Set[int]]) -> List[Set[int]]:
    """
    Removes sets that are subset of any other set in the given list.
    """
    scombs = sorted(combinations, key=len)
    output = []
    for i in range(len(scombs)):
        comb = scombs[i]
        if any(comb.issubset(scombs[j]) for j in range(i + 1, len(scombs))):
            continue
        else:
            output.append(comb)
    return output


def items_combinations(knapsack_capacity: int, items: Set[int],
                       items_weights: List[int]) -> List[Set[int]]:
    """
    Given a knapsack and a set of items, returns all possible combinations of items allocation.
    Combinations that don't use the maximum knapsack's capacity are ignored.
    """

    def recur(knapsack: Set[int], remaining_items: Set[int]):
        weight = sum(items_weights[i] for i in knapsack)
        if len(remaining_items) == 0:
            if weight <= knapsack_capacity and len(knapsack) > 0:
                return [knapsack]
            else:
                return []
        items = remaining_items.copy()
        i = items.pop()

        donttake = recur(knapsack, items)
        if weight + items_weights[i] <= knapsack_capacity:
            take = recur(knapsack.union([i]), items)
            return donttake + take
        else:
            return donttake

    return remove_subsets(recur(set(), items))


def main(knapsacks_capacities: List[int], 
         items_weights: List[int],
         items_values: List[int]) -> Tuple[int, List[Set[int]]]:
    """
    Returns the maximum value allocated in the list of knapsacks.
    Knapsacks are represented as set of items.

    * knapsacks_capacities: 1 x N
    * items_weights: 1 x M
    * items_values: 1 x M
    
    * output: (total value, items in each knapsack)
    """
    N = len(knapsacks_capacities)
    M = len(items_values)

    def total_value(knapsacks: List[Set[int]]) -> int:
        return sum(sum(items_values[i] for i in ksack) for ksack in knapsacks)

    def recur(remaining_items: Set[int], knapsacks: List[Set[int]],
              knapsack_idx: int) -> Tuple[int, List[Set[int]]]:
        """
        * output: the maximum value of the best possible allocation
        """
        if knapsack_idx >= N:
            value = total_value(knapsacks)
            return value, knapsacks
        combinations = items_combinations(knapsacks_capacities[knapsack_idx],
                                          remaining_items, items_weights)
        print("Combinations for sack {} and items {}: {}".format(
            knapsack_idx, remaining_items, combinations))
                
        if len(combinations) == 0:
            return recur(remaining_items,  knapsacks + [{}], knapsack_idx + 1)

        max_val, best_knapsacks = max((recur(
            remaining_items.difference(items), knapsacks + [items],
            knapsack_idx + 1) for items in combinations),
                                      key=lambda t: t[0])
        print("Best combinations for knapsack {}: {}".format(
            knapsack_idx, (max_val, best_knapsacks)))
        return max_val, best_knapsacks

    items = set(range(M))
    return recur(items, [], 0)


#### TESTS ####
#print(items_combinations(10, set(range(4)), [3,6,1,2]))
# [{3}, {2, 3}, {1, 3}, {1, 2, 3}, {0, 3}, {0, 2, 3}, {0, 1}, {0, 1, 2}]
# [{1, 2, 3}, {0, 2, 3}, {0, 1, 2}]  -> without subsets

print(main([10, 2], [3, 6, 1, 2], [5, 3, 2, 7]))
# (17, [{0, 1, 2}, {3}])

print(main([10, 5, 30, 15, 30], [13,8,12,10,13,6,11,9,12,7], [2,9,1,2,9,5,6,13,1,1]))
# (47, [{7}, {}, {0, 4}, {9, 5}, {1, 3, 6}])