作者buffalobill (水牛比爾)
看板puzzle
標題Re: [問題] 組裝三角
時間Tue Sep 1 09:28:22 2020
答案是1944
由下列直角三角形組成
(5,12,13)(6,8,10)(14,48,50)(15,20,25)(16,30,34)(21,28,35)(24,32,40)(27,36,45)
這題直觀上不難
從畢氏三元數出發
整理出邊長不超過50的直角三角形
共二十個
再將這二十個直角三角形的面積與共線關係
弄成一張圖：
https://i.imgur.com/9TQFv9x.png
問題就變成就這張圖裡選出面積總合最大的節點們
且相鄰的節點不得同時被選
也就是 Weighted Independent Set
WIS 是 NP-Complete 問題
意即目前的演算法
尚不存在比暴力更有效率的作法
不過20個節點的變化也就1048576種
對計算機而言是小 Case
甚至直接動手去排也應該不到半天就能找出解了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.148.94 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/puzzle/M.1598923704.A.43A.html