2

约翰尼需要为他的物理课项目制作一个矩形框。他买了 P cm 的铁丝和 S cm2 的特种纸。他想用所有的电线（12 个边）和纸（6 个边）来制作盒子。

约翰尼能做的最大盒子体积是多少？

输入

第一行包含 t，测试用例的数量（大约 10 个）。然后是 t 个测试用例。每个测试用例在一行中包含两个整数 P 和 S (1 ≤ P ≤ 40000, 1 ≤ S ≤ 20000)。您可以假设对于给定的输入案例总是存在一个最优解。

输出

对于每个测试用例，打印一个实数，它是 Johnny 可以制作的最大盒子体积，四舍五入到小数点后两位。

示例输入：

2
20 14
20 16

输出：

3.00
4.15

输出细节

第一种情况：最大盒子的尺寸可能是3、1和1。

第二种情况：最大盒子的尺寸可能是7/3、4/3和4/3。

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

4

4 回答 4

6

您实际上是在尝试解决：

maximize V=a*b*c

subject to constraints:

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

这是一个可以使用拉格朗日乘数解决的数学问题（将其余部分留给您作为练习 - 它主要是技术性的，如果小心缓慢地完成，应该不是问题）。

于 2012-12-05T22:13:54.290 回答
2

只是为了好玩，这是一个无微积分的答案。

考虑到约束：

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

我们可以将这些重写为：

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

或者

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

换句话说：解决方案位于与主轴相交的平面P/4和以原点为中心的球体的交点上，半径为P^2/16-S。这个交叉点是一个圆圈。从上面看，它看起来像一个椭圆，其中心与原点成 45 度，短轴沿同一条线。而且：

  1. 中心位于(P/12,P/12,P/12)。
  2. 半径为r = Sqrt(P^2/16-S - 3(P/12)^2)=Sqrt(P^2/24-S)。
  3. 圆位于垂直于(1,1,1)

因此，如果我们在圆上有一个点，它将相对于 的中心有一个位移(da,db,dc)。由于 3.，我们知道dc = -da - db. 此外，平方和必须等于半径的平方，所以：

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

现在，位移是圆的线性变换，因此我们可以将其参数化如下：

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

要求 的长度(da,db,dc)为r，我们得到：

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

要使其独立t，我们必须有6A^2 = 2B^2 = r^2，所以

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

所以

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

并且音量变为

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

其中 C 和 D 为正。显然，当cos 3t是时达到最大值-1，在这种情况下，音量为：

V = P^3/1728 - P(P^2/24-S)/24 + Sqrt(P^2/24-S)^3 Sqrt(6)/18
于 2012-12-06T05:18:39.763 回答
0

使用 具有多个约束的拉格朗日乘数。f(x,y,z) = xzy - L1*g(x,y,z) - L2*h(x,y,z) 其中 g(x,y,z)=x + y+ zP/4 和 h (x,y,z)=xy + yz + xz-S/2

然后你做df/dx = 0, df/dy = 0, df/dz = 0, df/dL1 = 0, df/dL2 = 0，你会得到5个方程如下：

  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

然后稍微算一下，你会发现 x = y = L2 从 1 2 和 3。然后 z = p - 2*L2 从 4 和 z = (s - 2*L2^2)/ 2*L2 从 5 . 现在你可以从上面两个方程计算L2的值了（还记得二次方程吗？）。体积为 V = xyz = L2 * L2 * (p - 2*L2)

于 2013-08-30T04:45:09.057 回答
-1

假设您在 codechef.com/problems/J7 遇到问题

python 2.7中的解决方案是

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)
于 2018-01-25T18:08:27.890 回答