→ BusterButter: 這種reduction的題目建議自己去看看proof自己推導一 09/23 00:56
→ BusterButter: 遍，不過我可以告訴你t的most significant digit是3 09/23 00:56
→ BusterButter: （因為vertex cover size = 3) 其他 digit都是2，所 09/23 00:56
→ BusterButter: 以算出來應該是3754 09/23 00:56
→ jacksoncsie: 好的 感謝提供建議 我自己再看一下 09/23 01:34
推 joywilliamjo: 答案是不是也可以是3697呢？ 09/23 07:47
推 alex391a: 這題跟3sat reduce到 subset sum很像 09/24 16:49
→ alex391a: 簡單來說就是要選三個點 09/24 16:49
→ alex391a: 然後為了cover所有edge 所以要選到每個至少要1（最多2） 09/24 16:49
→ alex391a: 所以下面就是為了讓1的那些可以加到2 09/24 16:49
→ alex391a: 所以答案是322222（四進位） 09/24 16:49
→ alex391a: 四進位是因為這題用四進位不會進位所以就不用那麼大的數 09/24 16:49
→ alex391a: 字 09/24 16:49
→ jacksoncsie: 感恩alex大 我戰友有找到類似題目 而且解答也差不多 09/24 21:34
→ jacksoncsie: 不過差一項2 感覺是跟 Graph 的 degree 有關 09/24 21:34
※ 編輯: jacksoncsie (114.37.85.220 臺灣), 09/24/2021 21:35:46
※ 編輯: jacksoncsie (114.37.85.220 臺灣), 09/24/2021 21:36:38
推 lienasd126: 可以問一下下方yi的意義是什麼？ 09/30 16:23