0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ But can you actually count for cases such as item 1, 1, 1, …, 1 n times? $\endgroup$
    – Raito
    Oct 27, 2017 at 19:44
  • $\begingroup$ @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.) $\endgroup$
    – D.W.
    Oct 27, 2017 at 19:47
  • $\begingroup$ 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$ ? $\endgroup$
    – Raito
    Oct 27, 2017 at 19:48
  • 1
    $\begingroup$ @Raito, that's right. $\endgroup$
    – D.W.
    Oct 27, 2017 at 19:50
  • $\begingroup$ 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? $\endgroup$
    – Raito
    Oct 27, 2017 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.