2

ジョニーは、物理学の授業プロジェクトのために長方形の箱を作る必要があります。彼はPcmのワイヤーとScm2の特殊紙を購入しました。彼は箱を作るためにすべてのワイヤー（12の端のために）と紙（6つの側面のために）を使いたいと思っています。

ジョニーが作ることができる箱の最大のボリュームは何ですか？

入力

最初の行には、テストケースの数（約10）であるtが含まれています。次に、t検定ケースが続きます。各テストケースには、1行に2つの整数PとSが含まれています（1≤P≤40000、1≤S≤20000）。与えられた入力ケースに対して常に最適なソリューションが存在すると想定することができます。

出力

テストケースごとに、ジョニーが作成できるボックスの最大ボリュームである実数を、小数点以下第2位に四捨五入して印刷します。

入力例：

2
20 14
20 16

出力：

3.00
4.15

出力の詳細

最初のケース：最大のボックスの寸法は3、1、1です。

2番目のケース：最大のボックスの寸法は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. 円は、に垂直な平面eにあります。(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

次に、少し計算すると、12と3からx= y = L2がわかります。次に、4からz = p-2 * L2、5からz =（s-2 * L2 ^ 2）/ 2*L2です。 。これで、上記の2つの方程式からL2の値を計算できます（2次方程式を覚えていますか？）。そして、ボリュームはV = xyz = L2 * L2 *（p-2 * L2）です。

于 2013-08-30T04:45:09.057 に答える
-1

codechef.com/problems/J7で問題が発生したと仮定します

Python2.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 に答える