1
$\begingroup$

(originally asked on StackOverflow)


Two recent questions on StackOverflow by the same author1 are generally solved by the same technique. This feels to me like it would be a studied and perhaps well-solved problem.

I would like to know what it might be called and where to find more information about it, assuming it is a well-known problem

This is my own phrasing of the question:

If we have a Set, $M$, of MultiSets, $M_1$ - $M_n$ made up of elements of Set $S$, and we have a MultiSet of components, $C$, also drawn from $S$, how do we find all subsets of $M$ such that the for each subset, the multiplicities of each element of $S$ in its union is no greater than the multiplicity of that element in $C$ ?2

For example, paraphrasing my own answer to the first question:

I think I understand that what you want would be for something like this:

const catalog= ["ad", "aab", "ace", "cd", "ba", "bd", "adf", "def"]
const components = ["a", "b", "a", "c", "d", "e"]

simultaneousItems (catalog, components) 

to yield

[
  ["ad", "ace"], ["ad", "ba"], ["ad"], ["aab", "cd"], ["aab"], ["ace", "ba"], 
  ["ace", "bd"], ["ace"],["cd", "ba"], ["cd"], ["ba"], ["bd"], []
]

where every array in the result is subset of catalog items that can be made together out of the components supplied. So, for instance, none of the output arrays contains "adf" or "def", since we have no "f" in the components, and none of them contain both "ad" and "aab" since we only have two "a"s in the component list.

Note that I'm using "abc" as a shorthand for the set containing the strings "a", "b", and "c".

The original problems seemed to be looking for maximal subsets, so there is one additional step, and that is perhaps an equally interesting problem, but I'm more curious about the version above.

Please don't look at my solution as any sort of algorithmic ideal. It was the first idea that came to mind.

Is this a well-known problem? There's some vague relationship to the Knapsack problem, and other packing problems, but I can't quite figure out what and where to search.


1 The first one is closer to what I think is the fundamental algorithmic question. I'm assuming the second one is closer to the real problem the OP is trying to solve. Without any feedback yet from the OP, I don't know for certain that my answers match the real need, but I find this an interesting question regardless.

2 More explicitly (and forgive me for being too far away from formal Math classes) if $C$ = ${\{S_1^{m(z_1)}, S_2^{m(z_2)}, ... S_j^{m(z_j)}\}}$ for some integer $j$, and $S_1$, $S_2$, ... $S_j$ in $S$, and if $N$ = ${\{M_{a_1}, M_{a_2}, ... M_{a_k}\}}$ is one of the subset of $M$ in the result, and ${∪\{{M_{a_1}, M_{a_2}, ... M_{a_k}}\}}$ = ${\{S_1^{m(x_1)}, S_2^{m(x_2)}, ... S_j^{m(x_j)}\}}$, then for all $i$, $x_i$$z_i$.

$\endgroup$
1
$\begingroup$

This problem (at least assuming you wish to find some sort of maximal subset) is simply the multidimensional knapsack problem, see e.g. "The Multidimensional Knapsack Problem: Structure and Algorithms" by Jakob Puchinger, Günther Raidl, Ulrich Pferschy.

To read that paper in your terminology, a quick translation. Your 'components' are known as resources, their multiplicities as capacities. The $i$th resource $S_i$ has capacity $c_i$. Each of your multisets $M_j$ is an item, and it consumes $w_{ij}$ of the $j$th resource. Thus $w_{ij}$ is the multiplicity of $S_i$ in $M_j$.

Finally in the optimization version that's studied in the linked paper we wish to know the most profitable solution. In this context each of your multisets $M_j$ (AKA items) has an associated profit $p_j$. The paper selects $x_j \in \{0, 1\}$ to determine whether item $j$ is part of the optimal solution, and thus solves the following problem:

\begin{align} \text{max }\;\; & z = \sum_{j=1}^n p_jx_j\\ \text{s.t. }\;\; &\sum_{j=1}^nw_{ij}x_j \leq c_i, \quad i =1,\dots,m,\\ &x_j\in\{0, 1\},\quad j = 1,\dots,n. \end{align}

Note that the paper uses $m$ as the number of components/resources and $n$ as the number of multisets/items.

$\endgroup$
3
  • $\begingroup$ Thank you. I will look at the paper and other links to MKP. Am I right that the simplification to the problem I describe is simply that ${p_i}$ is always $1$? $\endgroup$ – Scott Sauyet Dec 23 '20 at 22:46
  • $\begingroup$ Or at second thought, it's not so clear to me. I'm not looking for the single maximal subset but for the collection of sets that are maximal (in the sense that we cannot add additional items given the remaining resources.) I think it's still related, but I'm not sure about the details. Or without worrying about maximality (??), I'm looking for all subsets of items that can be built with the resources at hand. $\endgroup$ – Scott Sauyet Dec 23 '20 at 22:51
  • $\begingroup$ @ScottSauyet If you wish to know the largest set then yes $p_i$ is always some constant. I don't know if the paper describes a way to enumerate all valid solutions. $\endgroup$ – orlp Dec 23 '20 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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