Re: [問題] 組裝三角
看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者buffalobill (水牛比爾)時間4年前 (2020/09/01 09:28)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/2 (看更多)
答案是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://www.ptt.cc/bbs/puzzle/M.1598923704.A.43A.html
討論串 (同標題文章)
puzzle 近期熱門文章
PTT遊戲區 即時熱門文章
