5
$\begingroup$

You approach a bridge and see a troll. He throws down finite $n>0$ bags. Each bag, $B_i$, contain 1 or more of 4 possible buttons. $B_i$ contains $S_i \subseteq \{green, red, blue, yellow\} \land S_i \neq \emptyset$.

The contents of each bag is written on the bag - e.g. bag $B_i$ may have $\{red, green\}$ written on it.

The troll says, I know buttons are valuable in your neighbourhood and you can't get past me until you pick a set of bags such that you minimise $\frac{colours}{bags}$.

What is the best way to find the set of bags you should take?

Bonus points if you can tell me what this (NP?) problem is called.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Hi ${}{}{}{}{}$ $\endgroup$ – warspyking Aug 11 '15 at 4:20
  • $\begingroup$ Can there be 2 (or more) bags with identical contents? Is there any limit to $n$ (max or min)? Do we really want to minimize $\frac{colours}{bags}, or maximize it? Is it guaranteed that the set of all bags contains each colour at least once? $\endgroup$ – GentlePurpleRain♦ Aug 11 '15 at 4:32
  • $\begingroup$ @GentlePurpleRain There is no limit to n (but it is finite and positive). You want to minimise it colours/bags. No it's only guaranteed that each bag contains at least 1 button and at most 4 buttons - no bag contains more than one button of each colour. $\endgroup$ – d'alar'cop Aug 11 '15 at 4:39
  • $\begingroup$ What does $\frac{colours}{bags}$ mean? Total number of colours of all buttons you have (up to a maximum of 4) divided by $n$, or average number of colours per bag? $\endgroup$ – Rand al'Thor Aug 13 '15 at 20:05
  • $\begingroup$ @rand it's trying to express something like: "take the most bags and the fewest colours". - Total number of colours (max = 4) divided by the number of bags you are taking (you want lots of bags). $\endgroup$ – d'alar'cop Aug 14 '15 at 0:15
3
$\begingroup$

For each single colour check how many bags there are that only have that colour in it and pick the colour that has the most bags. If this number is equal to or larger than $n/4$ you're finished because this is the answer.

If not, for each combination of 2 colours check how many bags only have those colours and pick those colours that have the most bags. If this number is equal to or larger than $n/2$ you're finished because that is the answer.

If not, for each combination of 3 colours check how many bags only have those colours and pick those colours that have the most bags. If this number is equal to or larger than $n(3/4)$ you're finished because that is the answer.

If not pick all bags.

I think this at least gives the right answer but I doubt it is the best strategy because it is the most straight-forward strategy I would think.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ This algorithm requires 1 pass through all the bags, where you tally one of the fifteen combinations of colors. Followed by comparing several numbers, and then another pass where you choose the bags you want. The number of steps is linear in number of bags, but exponential in number of buttons. If the number of buttons is small, it's highly efficient. $\endgroup$ – user3294068 Aug 11 '15 at 13:24
  • $\begingroup$ Slight issue. If you have $n/4$ bags with a red button and $3n/4$ bags with a blue and a yellow button, then your algorithm would pick the first group, but the best choice would be the second group. You need to compare all fifteen numbers to see which has the best ratio. $\endgroup$ – user3294068 Aug 11 '15 at 17:11
  • $\begingroup$ @user3294068 no. If there was the case there were 3/4 n of yellow and blue that would automatically mean that if you only would pick blue or yellow that they have far more than n/4 of them. So they would be a pick in the first round. You can't have 2 colours in three quarter of the bags without at least one of those colours having 3/8 n of them $\endgroup$ – Ivo Beckers Aug 11 '15 at 17:16
  • $\begingroup$ In my scenario, there are $n/4$ bags wit ha single color in them, and $3n/4$ bags with two colors. The solution says that if you have $n/4$ bags with the same single color, then you are done and don't need to look at bags with multiple colors. That is incorrect. $\endgroup$ – user3294068 Aug 11 '15 at 17:41
  • $\begingroup$ It is correct. In you situation you would pick all bags that are blue or yellow, whichever has most bags because it would beat red. At worst there are both 3/8 blue and 3/8 yellow. If you would pick one of those colors you get exactly the same score as picking the 2 colors having 3/4 $\endgroup$ – Ivo Beckers Aug 11 '15 at 17:45
0
$\begingroup$

If we take bags without reducing the number of colors from the first combination excluding a given color the ratio won't be minimized, so we must jot down which bags have only a given color combination (there are 15), which must be repeated for the other combinations, and choose the one minimizing the ratio by excluding all the others with an unwanted color.

Improve this answer
$\endgroup$

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.