Enumerate all maximal subset of a weighted knapsack

Question

Given a knapsack $A$ composed of $(u_i, v_i)$-item where $u_i$ is the item identifier and $v_i$ is the weight of the item.

I call a maximal subset when you consider a subset $S$ of $A$ where the sum $R(S)$ over $v_i$ in this subset is less or equal than $P_{max}$ and if you try adding any item $(u_j, v_j) \in A \setminus S$ (if that's not empty) in $S$, then it'll exceed the $P_{max}$ limit, that is: $\forall (u_j, v_j) \in A \setminus S, R(S \cup \{ u_j, v_j \}) > P_{max}$.

I wrote this Python algorithm to compute such an enumeration:

def determine_available(bag, Pmax):
    return [(u, p) for (u, p) in bag if p <= Pmax]

def enumeration(bag, Pmax):
    if Pmax == 0:
        return []

    cur = []
    for v, p in determine_available(bag, Pmax):
        r = Pmax - p

        if not determine_available(bag, r):
            cur.append([v])
        else:
            for pos in enumeration(bag, r):
                cur.append([v] + pos)

    return cur

print(enumeration([(4, 20), (2, 2)], 100)) # for example.

Pseudo-code:

enumeration (bag: set of available items, Pmax)
     if Pmax = 0
     then return empty list

     current_subsets <- empty list
     for all available and usable item of identifier v, weight p
     do 
          r = Pmax - p
          if enumerate(bag, r) is empty
          then add the singleton [v] as a subset in current_subsets
          else
               for all subset of enumerate(bag, r)
                  add in current_subsets: [v] + subset
     done
     return current_subsets

Unfortunately, I would like to compute only distinct solutions without removing duplicates after the enumeration. Is there any way to do this?

Bonus question: how to enumerate them in an iterative way?

Answer 1

There might be exponentially many such maximal subsets, so there is in general no efficient way to enumerate all of them.

It's not hard to write a recursive algorithm to enumerate all subsets. There are only two cases:

• The subset doesn't contain item 1. It consists of a maximal subset of items 2,3,... that sum to $P_\max$ or less.

• The subset does contain item 1, plus a maximal subset of items 2,3,... that sum to $P_\max-v_1$ or less.

You can enumerate all subsets of the first type with a recursive call to the procedure, and enumerate all subsets of the second type with a second recursive call. The base case: if $P_\max \le 0$ or $A$ is empty, then the only such subset is the empty set.