Optimal Combination of Random Selections

miarki

New member
Joined
Oct 2, 2014
Messages
2
Hi there,

First time posting here, since I ran into a tricky problem I haven't been able to solve myself. I quickly tried to search these forums for similar problems but couldn't find any. Any help is much appreciated.

We have three types of "chests" and three types of "gems". Lets call the chest types A, B and C and the gems red, blue and yellow.

A chest has always only one (1) gem inside it. Different chest types have different chances of yielding a certain coloured gem for each individual chest.

Lets say:

Chest A: 50% chance for RED gem, 30% chance for BLUE gem, 20% chance for YELLOW gem
Chest B: 20% chance for RED, 70% for BLUE, 10% for YELLOW
Chest C: 30% RED, 30% BLUE, 40% YELLOW

The actual problem:

Whats the optimal combination of chests to gain expected total of e.g. 30 RED gems, 45 BLUE gems and 40 YELLOW gems?

My progress so far:

We need 30+45+40 = 115 gems, and since each chest yields only 1 gem, the amount of chests we need is >= 115. Closer to 115 the better, since we want to find the optimal combination of chests.

We know that the expected yields for chests are (red/blue/yellow)
A: 0,5 / 0,3 / 0,2
B: 0,2 / 0,7 / 0,1
C: 0,3 / 0,3 / 0,4

I made a simple Excel to try to find the best solution manually and then try to determine a formula of sorts, but no success so far. The best manual result I could find was
0 amount of chest A (0 RED / 0 BLUE / 0 YELLOW)
24 of chest B (4.8 / 16.8 / 2.4)
94 of chest C (28.2 / 28.2 / 37.6)

= 118 chests with 33 RED gems, 45 BLUE gems and 40 YELLOW gems. Yes, I'm using fractions of gems here, even though I probably shouldn't, but this is the best answer I've been able to get so far. I tried to google for similar math problems, but the closest one I found was the Knapsack problem, which does seem to be somewhat similar, but not similar enough at least for me to form a new formula based on it. Oh, and instead of the actual answer, I'm more interested in finding a solution (or solutions?) to solve this and similar problems.

Thank you.

- Mike
 
Hi Mike,

See if you can get somewhere with

RED gems___: 0.5 NA + 0.2 NB + 0.3 NC \(\displaystyle \ge\) 30
BLUE gems__: 0.3 NA + 0.7 NB + 0.3 NC \(\displaystyle \ge\) 45
YELLOW gems: 0.2 NA + 0.1 NB + 0.4 NC \(\displaystyle \ge\) 40
TOTAL BOXES: 1.0 NA + 1.0 NB + 1.0 NC = T \(\displaystyle \ge\) 115
Where NA, NB, and NC are the total number of boxes of type A, B, and C respectively and T is the Total number of boxes.

The way to solve problems like this is to first ignore the last equation and solve for the equalities in the other three. Then start working with the inequalities (solutions should contain an integer number of boxes (and gems), so maybe you can round up NA and round down NB). But then, for a general problem, maybe just the answer obtained would be sufficient. Depends on what you (or your instructor) want.

You will often find that the last equation is satisfied automatically, i.e. let T be the sum of the totals of the boxes and it will be greater that 115.

Edit to add: As a point of information, the three top equations with the equal sign define three planes in (NA, NB, BC) space. Thus the inequality is that you are restricted to one particular side of the plane. This may or may not help in developing the solution but I find it easier to visualize the solution this way.
 
Last edited:
Thanks!

I finally got it. Had some problems 'cause first I got some negative values for some variables and so on. Then I ran into something called linear programming and after that I was able to find tutorials to help me out with this. Now I got a nice little Excel sheet ready to solve any problems like this. Thanks for helping me to find the right direction! :)

- Mike
 
Top