algorithm - 我们如何通过算法计算出具有最大可能体积的盒子？

Question

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.

这是来自 www.codechef.com 的练习题。名称是“The Best box”。我不想要这个代码。我只想知道我们如何解决这个问题？任何帮助，将不胜感激。提前致谢。

Answer 1

你实际上是想解决:

maximize V=a*b*c

subject to constraints:

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

这是一个可以使用 lagrange multipliers 解决的数学问题(将剩下的部分留给您作为练习 - 它主要是技术性的，如果小心谨慎地慢慢完成，应该不会有问题)。