Toy Builder

PuzzlOR Toy Builder Problem

Toy	Blue Blocks	Green Rods	Red Wheels
Airplane	3	2	1
Helicopter	2	4	1
Car	1	2	4
available	25	29	30

---

$maximize \ \ \$7A+\$8H+\$5C$

$$ \begin{align} 3A+2H+C\le25 \\ 2A+4H+2C\le29 \\ A+H+4C\le30 \end{align} $$

$$ A,H,C\ge0 $$

---

Because of the resource constraints, we can also put an upper limit on each variable.

$$ \begin{align} 0\le A\le 8 \\ 0\le H\le 7 \\ 0\le C\le 7 \end{align} $$

This problem is small enough to be solved with a brute force search in Python; only (9 x 8 x 8) = 576 candidate solutions to check. On the first pass, print out feasible solutions with profit >= 56, which is an easily obtained lower bound on max profit (by making Airplanes only). The printed solutions included profits above 70, so that became the new profit cut-off for printing solutions on the second pass.

In [1]:

for A in range(9):
    for H in range(8):
        for C in range(8):
            Profit = 7*A + 8*H + 5*C
            Blue = 3*A + 2*H + C
            Green = 2*A + 4*H + 2*C
            Red = A + H + 4*C
            if (Profit >= 70) and (Blue <= 25) and (Green <= 29) and (Red <= 30):
                print(A,H,C,Profit)

3 3 5 70
4 2 6 74
4 3 4 72
4 4 2 70
5 1 6 73
5 2 4 71
5 2 5 76
5 3 3 74
5 4 1 72
6 0 6 72
6 1 4 70
6 1 5 75
6 2 3 73
6 3 1 71

Maximum Profit = $76; obtained by building 5 Airplanes, 2 Helicopters, 5 Cars.