Gegeben ein Array von n ganzen Zahlen. Suchen Sie die minimale Länge der Teilmenge mit dem maximalen OR-Wert unter allen Teilmengen des gegebenen Arrays.Maximale OR-Werte in allen Teilmengen des Arrays
Wie man das löst ??
Das maximale OR ist nur das OR aller Elemente, das einzige wirkliche Problem ist das Auffinden der kleinsten Teilmenge, die auf diesen Wert ORs hat.
Dies ist die Suchversion des Set Cover-Problems, sowohl in dem Sinne, dass es offensichtlich dadurch gelöst werden kann, dass es als eine Instanz der Suchversion von Set Cover behandelt wird, als auch als Set Cover-Instanz in Bezug auf dieses Problem, so ist es NP-schwer (nicht NP-vollständig, weil es kein Entscheidungsproblem ist).
Sie könnten das mit Integer Linear Programming lösen, SAT lösen (kostet mehrere Abfragen, da SAT nicht optimiert), Dynamic Programming und zweifellos andere Techniken.