4. 金幣問題

問題敘述

有一個國王想要徵求一個聰明的智者，因此他出了一道難題：在皇宮中的N個房間，每間房間都放有一個金幣，其中有些房間彼此間有直接通道。國王規定每個參加的人可以進入任一房間，並取走房間中的金幣，但不能同時取走有直接通道的兩個房間中的金幣。滿足此規定下，必須儘可能取最多的金幣，請問其中取到最多金幣的方法所得金幣數目為多少個?

舉例說明如下，有四個房間，分別以編號1到4表示，其中編號1和編號3有直接通道，編號1和編號4有直接通道。其他房間之間皆無直接通道。儘可能取金幣的方法之一為取房間1及房間2的金幣，另一個方法為取房間2, 3, 及4的金幣，共兩種取法，其中取到最多金幣的方法可取到3個金幣。