CODEWITHSUNDEEP
algorithm
kusur
kusur

Reputation: 618

How can we algorithmicaly calculate the box with maximum possible volume?

Johnny needs to make a rectangular box for his physics class project. He has bought P cm of wire and S cm2 of special paper. He would like to use all the wire (for the 12 edges) and paper (for the 6 sides) to make the box.

What is the largest volume of the box that Johnny can make?

Input

The first line contains t, the number of test cases (about 10). Then t test cases follow. Each test case contains two integers P and S in a line (1 ≤ P ≤ 40000, 1 ≤ S ≤ 20000). You may assume that there always exists an optimal solution for the given input cases.

Output

For each test case, print a real number that is the largest volume of the box that Johnny can make, rounded to two decimal places.

Example Input:

2
20 14
20 16

Output:

3.00
4.15

Output details

First case: the dimensions of the largest box may be 3, 1 and 1.

Second case: the dimensions of the largest box may be 7/3, 4/3 and 4/3.

This is a practice problem from www.codechef.com. The name is "The Best box". I don't want the code for this. All I want to know is that how do we solve the problem? Any help would be appreciated. Thanks in advance.

Upvotes: 2

Views: 6331

Answers (4)

Chinmesh Manjrekar
Chinmesh Manjrekar

Reputation: 9

assuming you got the problem at codechef.com/problems/J7

the solution in python 2.7 is 

T = int(input())
for i in range(T):
    P = raw_input().split()
    S = int(P[1])
    P = int(P[0])
    V = (P**3)/1728.00 - P*( (P**2)/24.00-S)/24.00 + (((P**2)/24.00-S)**1.5)*(6**0.5)/18
    print("%.2f"%V)

Upvotes: -1

Zhongyuan
Zhongyuan

Reputation: 56

Using Lagrange Multiplier with multiple constraints. f(x,y,z) = xzy - L1*g(x,y,z) - L2*h(x,y,z) where g(x,y,z)=x + y+ z-P/4 and h(x,y,z)=xy + yz + xz-S/2

Then you do df/dx = 0, df/dy = 0, df/dz = 0, df/dL1 = 0, df/dL2 = 0, you will get 5 equations as follows:

  1. yz = L1 + L2*(y+z)
  2. xz = L1 + L2*(x+z)
  3. xy = L1 + L2*(x+y)
  4. x + y + z = p
  5. xy + yz + xy = s

Then with a little bit math, you will find out x = y = L2 from 1 2 and 3. Then z = p - 2*L2 from 4 and z = (s - 2*L2^2)/ 2*L2 from 5. Now you can calculate the value of L2 from the above two equations(still remember Quadratic equation?). And the volume is V = xyz = L2 * L2 * (p - 2*L2)

Upvotes: 0

Jeffrey Sax
Jeffrey Sax

Reputation: 10323

Just for fun, here's a calculus-free answer.

Considering the constraints:

4a+4b+4c = P 
2ab + 2ac + 2bc = S

We can rewrite these as:

a+b+c = P/4
(a+b+c)^2 - (a^2+b^2+c^2) = S

or

a+b+c = P/4
a^2+b^2+c^2 = P^2/16 - S

In other words: the solutions lie on the intersection of a plane that cuts the main axes at P/4 and a sphere centered at the origin with radius P^2/16-S. This intersection is a circle. Looking at it from above, it looks like an ellipse with its center at 45 degrees from the origin with the short axis along this same line. Moreover:

  1. The center is at (P/12,P/12,P/12).
  2. The radius is r = Sqrt(P^2/16-S - 3(P/12)^2)=Sqrt(P^2/24-S).
  3. The circle lies in a plan e perpendicular to (1,1,1)

So, if we have a point on the circle, it will have a displacement relative to the center of (da,db,dc). Because of 3., we know that dc = -da - db. Also, the sum of the squares must be equal to the square of the radius, so:

r^2 = da^2 + db^2 + (da+db)^2
    = 2(da^2 + db^2 + da db)

Now, the displacements are a linear transformation of a circle, so we can parameterize it as follows:

dc = -2A cos t
da = A cos t + B sin t
db = A cos t - B sin t

Demanding that the length of (da,db,dc) is r, we get:

da^2 + db^2 + dc^2
    =   A^2 cos^2 t +  B^2 sin^2 t + 2AB cos t sin t
      + A^2 cos^2 t +  B^2 sin^2 t - 2AB cos t sin t
     + 4A^2 cos^2 t
    =  6A^2 cos^2 t + 2B^2 sin^2 t

For this to be independent of t, we must have 6A^2 = 2B^2 = r^2, so

A = r / sqrt(6)
B = r / sqrt(2)

and so

da = r/sqrt(6) cos t + r/sqrt(2) sin t
db = r/sqrt(6) cos t - r/sqrt(2) sin t

and the volume becomes

V = (P/12 + da)(P/12 + db)(P/12 - da - db)
  = P^3/1728 + (da db - da(da + db) - db(da + db))P/12 - da db (da + db)
  = P^3/1728 - (da^2 + db^2 + da db)P/12 - da db (da + db)
  = P^3/1728 - P r^2/24 - da db (da + db)
  = C - (r^2/6 cos^2 t - r^2/2 sin^2 t) 2 r/sqrt(6) cos t
  = C - r^3 sqrt(6)/18 (cos^2 t - 3 sin^2 t) cos t
  = C - D (4 cos^2 t - 3 cos^2 t - 3 sin^2 t) cos t
  = C - D (4 cos^3 t - 3 cos t)
  = C - D cos 3t

where C and D are positive. Clearly, the maximum is reached when cos 3t is -1, in which case the volume is:

V = P^3/1728 - P(P^2/24-S)/24 + Sqrt(P^2/24-S)^3 Sqrt(6)/18

Upvotes: 2

amit
amit

Reputation: 178481

You are actually trying to solve:

maximize V=a*b*c

subject to constraints:

4a+4b+4c = P 
2ab + 2ac + 2bc = S

This is a mathematical problem that can be solved using lagrange multipliers (Leaving developing the rest to you as an excercise - it is mostly technical, and if done slowly with care, shouldn't be a problem).

Upvotes: 6

Related Questions