puzzleUp風味題 Vol.5
【組裝三角】
給予50個線段，長度分別為1~50。
組成任意數量的直角三角形。
問這些直角三角形的最大總合面積為？
線段不能裁接凹折
三角形之間不能共線
若題目給1~20的線段，則答案為162
(3,4,5)(8,15,17)(12,16,20)

長度1跟2是不可能組成直角三角形的，無視就好:)

程式列出畢氏三元數，再用紙筆初步湊出 1932如果不考慮畢氏三元數可能出現的潛在關係programUp 起來是個 weighted independent set 問題要處理的圖是這個 https://imgur.com/VyVurkQ.png

1932還差一點點哦

上面那張圖多算了 (20, 48, 52)，不過跑起來結果一樣因為沒有用到那組是有沒考慮到的組裝方式嗎(思找到問題了，1944

1944正解

新的圖要手算感覺麻煩許多

我找到 1944, 還不確定是不是最大hmmmm啊, 找到 1932 了...還在想這種 local max 應該要出現的我是整理出 (9,12,15) (12,16,20) (15,20,25) 最多取其一從這裡去找, 1944 是選 (15,20,25) 得到的最大值1932 則是都不選的 local max主要是 (30,40,50) 的位置太尷尬, 取和不取的條件不夠多又被 (14,48,50) (18,24,30) (24,32,40) 兩邊夾從那邊出發的分支完全動不到上五樓提到的那一團

我是用 (m^2-n^2, 2mn, m^2+n^2) 找畢氏三元數沒注意到這只保證可以找出互質的，所以才算出 1932 XD那張圖裡列的是用這個公式可以找出的那些

哦, 你是找所有 (m, n) 而不是用基本三元數乘 k 倍...

對XD

所以就正好漏掉了包含 (15,20,25) 的幾個這樣嗎 XD

有包含 (12,16,20)，不過找最大值的時候不會取到