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?