I am trying to design an algorithm that will generate the full list of ways to minimally satisfy multiple requirements, given information on how the individual requirements are fulfilled.
For example, let's say you can either have (1) or not have (0) four different foods: Apple, Banana, Carrot, Donut.
Requirement 1 says "You must have an Apple and a Banana." (1,1,0,0) satisfies this. So do (1,1,1,0), (1,1,0,1), and (1,1,1,1), but these are not minimal solutions, since you could take away the Carrot and/or Donut and still satisfy it.
Requirement 2 says "You must have three foods." (1,1,1,0), (1,1,0,1), (1,0,1,1), and (0,1,1,1) are all minimal solutions for this. (1,1,1,1) is not minimal.
I already have ways of generating the minimal satisfying solutions above. They aren't optimal but the search space for each individual requirement is small enough that it doesn't matter. Here's where it gets sticky: generating a list of ways to minimally satisfy both at once.
The brute-force approach to minimally satisfying both at once is then easy, as long as no requirement turns from satisfied to unsatisfied by adding a food (i.e. there's no requirement that says "You must not have a Donut"). Simply (first) look at all combinations of successful arrays, one from each requirement, and take the maximum of each element. For example, combine (1,1,0,0) from Requirement 1 with (1,0,1,1) from Requirement 2 to get (1,1,1,1) to satisfy both. Then (second) prune out non-minimal solutions by comparing each array that satisfies all requirements against each other to get the minimal solutions (1,1,0,1) and (1,1,1,0).
But this is very slow! The runtime grows very quickly with the number of requirements, or successful arrays per requirement. And it generates a lot of redundant output before pruning (for example, (1,1,0,0) plus either (1,0,1,1) or (0,1,1,1) both make (1,1,1,1)).
I'm at a bit of a loss as to how to attack this differently so as to avoid searching every combination, and would appreciate any help. I only have minimal theoretical-CS training and feel like there's probably some terminology or analogous known algorithm I'm not aware of.