※ 引述《initial13254 (瑟約)》之銘言：
: 以前有上過一個演算法的課
: 有一個很鳥的作業
: 題目是有個老闆想送人冬瓜磚 共N個 冬瓜磚長寬高10公分
: 他想用包裝紙這些冬瓜磚 而且包裝起來要
:
: 1.包裝成一個x*y*z的長方體
: 2.包裝紙越少越好
: 3.不能有空隙
:
: 一旦N是質數例如19 你包裝起來必定是一個190*10*10的超長超細長方體
: 雖然我覺得題目可能有少打什麼或有錯誤 不過課本上面就是這麼寫的
:
: 起初並沒有什麼難 但隨者數字越來越大 就越不知道怎麼設計
: 當N是4個質數相乘之前我都還行 5個質數相乘我就炸了
: 開始亂瞎猜 什麼開立方根阿 先乘個3看看阿 反正跟數學邏輯沒什麼關係了
:
: 最後老師上課講解告訴我 : 題目好像怪怪的 只好用暴力破解法喔啾咪
: 推 e5a1t20: 滿足正整數xyz=N，求xy+xz+zy最小，只求表面積還是包裝 12/10 21:07
: → e5a1t20: 紙還要長方形把冬瓜磚包起來？ 12/10 21:07
: → e5a1t20: 求最小N/x+xN/k+k，讓k=xy，這樣算起來暴力解的複雜度大 12/10 21:25
: → e5a1t20: 概比N的因數數量^2小 12/10 21:25
我剛剛在看角卷綿芽昨天的SC時候想到這問題
https://pbs.twimg.com/media/EoUJcfJUYAE8uhJ.jpg
這個演算法問題其實還滿有趣的啊
假設我們考慮一個比較廣泛的問題：
給定兩個整數 N 和 n，
求所有滿足 x_1*x_2*....x_n = N 的正整數組合 (x_1,x_2,...,x_n) 中，
n
Σ N/x_i 的最小值
i=1
原來的那個包裝問題就是這問題在 n=3 的特例
假設給定兩整數N,n所能得到的最小值是 f(N,n)，則我們有
f(N,n) = min N/u + u*f(N/u, n-1)
u | N (意即u是N的因數)
f(N,1) = 1
f(1,n) = n
這作法時間複雜度是 o( (N的因數數量)^2*n )
硬爆我覺得就算用backtracking在n稍大都會炸開來

摁摁 我想也是這樣

為什麼會在看羊的時候想到啊…

不就尻完的時候開始思考宇宙的真理嗎

想了一下 所以要先對N做質因數分解 並將N的質因數任意分為三組數組 並且確保三組乘積的標準差為最小吧？

推賢者XD 這分析漂亮 受教了