陣列的所有子集中的最大OR值

Question

給定一個n個整數的數組。查找給定數組的所有子集中具有最大OR值的子集的最小長度。

如何解決這個問題？

Answer 1

最大的或者只是所有項目的或，唯一真正的問題是找到那個或那個值的最小子集。

這是集合封面問題的搜索版本，兩者的含義明顯可以通過將其視爲集合封面的搜索版本實例來解決，也就是說您可以編寫一個集合封面實例在這個問題上，所以它是NP難（不是NP完全的，因爲它不是一個決策問題）。

你可以用整數線性規劃解決這個問題，解決SAT問題（由於SAT沒有優化而花費幾個查詢），動態規劃，以及其他技術。