Algorithmus zur Kategorisierung von Werten

Question

Was wäre der beste Algorithmus, um dieses Problem zu lösen? Ich habe ein paar Stunden mit diesem Problem verbracht. Aber konnte es nicht klären.

Ein Mann kaufte eine Halskette und plante, sie in zwei Teile zu zerlegen, so dass die durchschnittliche Helligkeit jedes Stückes größer oder gleich dem Originalstück sein sollte.

Die Kriterien für die Unterteilung der Ketten sind

1.Die Unterschied in der Anzahl der Perlen zwischen den beiden Sätze Perlen nicht größer als 10% der Anzahl der Perlen in der ursprünglichen Kette oder 3 ist, je nachdem, was höher sein sollten.

2.Der Unterschied zwischen der Anzahl der Perlen in 2 Halsketten sollte minimal sein.

3. Wenn die durchschnittliche Helligkeit eines der Halsketten kleiner ist als die durchschnittliche Helligkeit des ursprünglichen Satzes, wird 0 als Ausgabe zurückgegeben.

4. Zwei Halsketten sollten ihre durchschnittliche Helligkeit größer als die ursprüngliche haben und der Unterschied zwischen der durchschnittlichen Helligkeit der beiden Stücke ist minimal.

5.Die durchschnittliche Helligkeit jedes Stückes sollte entweder größer oder gleich dem Originalstück sein.

Answer 1

Dieses Problem ist ziemlich schwer effizient (irgendwo in NP).

Angenommen, Sie hatten einen Satz, der nach X gemittelt wurde. Das heißt, .

Angenommen, Sie brechen in Gruppen bis die jeweils in jedem Satz zu S und T mit s und t Artikel mitteln.

Sie können mathematisch beweisen, dass, wenn einer der Mittelwerte, S oder T größer als X ist, der andere der beiden muss kleiner sein als X.

Daher müssen die beiden Sätze genau die gleiche Helligkeit haben, denn nur so sind Ihre Bedingungen erfüllbar.

Wenn Sie dies wissen, enden Sie mit dem sumset sum Problem - Sie möchten eine Teilmenge finden, die genau zur Hälfte der Summe des gesamten Satzes addiert. Das ist ein bekanntes Problem. (Es wurde als NP klassifiziert. Und es ist nicht genau dasselbe wie das Subset-Summenproblem, aber wenn man den Durchschnitt des gesamten Sets von jedem der Helligkeitswerte subtrahiert, wird das Lösen des Subset-Summenproblems deine Antwort geben umgekehrt, um zu sehen, wie Sie die Teilmenge Summe Problem von Ihrem Problem lösen können.)

Daher gibt es keine schnelle Möglichkeit, dies zu tun - nur Näherungen oder exponentielle Laufzeiten ... Allerdings kann this helfen. Es erwähnt besser Laufzeiten, wenn Ihre Gewichte (in Ihrem Fall, Helligkeitsstufen) begrenzt sind