拼圖

組裝三角 - 拼圖

Linda avatarLinda · 2020-08-31

Table of Contents

puzzleUp風味題 Vol.5

【組裝三角】
給予50個線段，長度分別為1~50。
組成任意數量的直角三角形。
問這些直角三角形的最大總合面積為？

線段不能裁接凹折
三角形之間不能共線

若題目給1~20的線段，則答案為162
(3,4,5)(8,15,17)(12,16,20)

--
拼圖

All Comments

Margaret avatarMargaret2020-09-03
長度1跟2是不可能組成直角三角形的，無視就好:)
Daniel avatarDaniel2020-09-08
程式列出畢氏三元數，再用紙筆初步湊出 1932
Jacob avatarJacob2020-09-11
如果不考慮畢氏三元數可能出現的潛在關係
programUp 起來是個 weighted independent set 問題
Christine avatarChristine2020-09-13
要處理的圖是這個 https://imgur.com/VyVurkQ.png
Ina avatarIna2020-09-17
1932還差一點點哦
Leila avatarLeila2020-09-17
上面那張圖多算了 (20, 48, 52)，不過跑起來結果一樣
Ivy avatarIvy2020-09-17
因為沒有用到那組
是有沒考慮到的組裝方式嗎(思
Olive avatarOlive2020-09-20
找到問題了，1944
Zanna avatarZanna2020-09-23
1944正解
Rae avatarRae2020-09-23
新的圖要手算感覺麻煩許多
Olga avatarOlga2020-09-28
我找到 1944, 還不確定是不是最大
hmmmm
Gilbert avatarGilbert2020-10-03
啊, 找到 1932 了...還在想這種 local max 應該要出現的
Genevieve avatarGenevieve2020-10-06
我是整理出 (9,12,15) (12,16,20) (15,20,25) 最多取其一
從這裡去找, 1944 是選 (15,20,25) 得到的最大值
1932 則是都不選的 local max
Harry avatarHarry2020-10-07
主要是 (30,40,50) 的位置太尷尬, 取和不取的條件不夠多
Leila avatarLeila2020-10-08
又被 (14,48,50) (18,24,30) (24,32,40) 兩邊夾
George avatarGeorge2020-10-12
從那邊出發的分支完全動不到上五樓提到的那一團
Jessica avatarJessica2020-10-14
我是用 (m^2-n^2, 2mn, m^2+n^2) 找畢氏三元數
沒注意到這只保證可以找出互質的，所以才算出 1932 XD
Gilbert avatarGilbert2020-10-18
那張圖裡列的是用這個公式可以找出的那些
Hedy avatarHedy2020-10-20
哦, 你是找所有 (m, n) 而不是用基本三元數乘 k 倍...
Charlotte avatarCharlotte2020-10-25
對XD
Skylar DavisLinda avatarSkylar DavisLinda2020-10-25
所以就正好漏掉了包含 (15,20,25) 的幾個這樣嗎 XD
Agnes avatarAgnes2020-10-27
有包含 (12,16,20)，不過找最大值的時候不會取到