给定一个逻辑电路，可以将其建模为有根树 - 叶子是主要输入，内部节点是门，根是电路的单个输出。每个门可以由高或低电源电压供电。由较低电源电压供电的栅极消耗的功率较少，但具有 输出信号较弱。您希望在确保电路可靠的同时最大限度地降低功耗。为确保可靠性，不应让一个由低电源电压供电的栅极驱动另一个由低电源电压供电的栅极 电源电压。所有门在连接到低电源电压时消耗 1 纳瓦，在连接到高电源电压时消耗 2 纳瓦。
设计一种高效算法，将逻辑电路作为输入并为每个门选择电源电压，以最大限度地降低功耗，同时确保可靠运行。
这道题我的想法是，可以用greedy或者Dynamic来解决。但是我很困惑我可以从哪里开始思考这个问题。 请帮忙。
最佳答案
根据“你不应该让一个由低电源电压供电的门驱动另一个由低电源电压供电的门”的要求，我们得到我们的任务是在树中找到一个最大的独立集(可能减去叶子，我不知道他们是否被认为是有动力的)。
虽然该问题对于一般图来说是 NP-hard 问题，但对于树来说可以快速有效地解决。你可以阅读这个simple 3-page article了解详情。
关于algorithm - 最小功率要求算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12128056/