c# - 如何获得枚举标志值的最短表示？

Question

我想生成可能产生特定枚举值的枚举字段的最短（或最短之一）组合。完成此任务的最佳算法是什么？

例如，假设我有枚举：

enum MyEnum
{
    One = 1, 
    Two = 2,
    Three = One | Two,
    Four = 4,
    Six = Two | Four,
    Eight = 8,
    All = One | Two | Four | Eight
 }

现在例如对于7我希望我的函数输出的值"One | Six"或"Three | Six"。

编辑：当然Three | Four也是一个有效的输出。

Answer 1

你基本上要求的是最小集合覆盖，一个被称为 NP Complete 的问题。幸运的是，这并不意味着您无法解决诸如此类的小情况。您还可以O(logn)通过贪心算法获得近似值。

如果您的枚举值没有特定的结构，那么对于一般的精确解决方案，您将无法比蛮力做得更好。如果您知道您的枚举具有特定的结构，那么您通常可以通过图形分区或 CSP + 回溯等方式获得更好的结果。