# Enumerate all maximal subset of a weighted knapsack

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?

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.

• But can you actually count for cases such as item 1, 1, 1, …, 1 n times? Oct 27, 2017 at 19:44
• @Raito, the question asks for a maximal subset. A subset, by definition, cannot have a repeated item. (But if you want to allow repeats, it is easy to modify this approach to handle that alternative problem statement. You just need to modify the second bullet in my answer -- I'll let you work out how.)
– D.W.
Oct 27, 2017 at 19:47
• That's right, sorry. Am I right in thinking that it suffices to consider that the list will contain item 1 plus a maximal list of items 1, 2, … that sum to $P_{\textrm{max}} - v_1$ ? Oct 27, 2017 at 19:48
• @Raito, that's right.
– D.W.
Oct 27, 2017 at 19:50
• I wrote an implementation of your proposal, though, I am unable to get an answer due to recursion limits. What could I be doing wrong? Oct 27, 2017 at 20:01