reduziert die Anzahl der Teilmengen von

Question

hier das Problem. Sagen wir, wir haben eine große Menge von N Elementen. Wir haben auch eine große Liste von M kleinen Mengen von Elementen und die kleinen Sätze können sie schneiden, was bedeutet, dass sie eine Anzahl von gleichen Elementen haben können: SE (1-> M). Jetzt wäre es unser Ziel, die minimale Anzahl von Teilmengen von gegebenen n Elementen zu finden (wobei n < N), die die maximale Anzahl der ursprünglichen kleinen Sätze von Elementen enthalten würde.

Zum Beispiel:

(1 2 3 4 5 6 7 8 9 10 11 12) = big set with N = 12 

(1 3 7 8) 
(1 2 3 10 12) 
(4 5 7 9) 
(6 10 12) 
(3 5 9 12) 
(2 4 6 8) 
(1 2 3 4) 

lassen Sie uns sagen, dass die Summe der Sätze nicht 9 Elemente nicht überschreiten (

dann wäre eine Lösung sein:

subset1 
(1 3 7 8) 
(1 2 3   10 12) 
( 3 5  9 12) 
subset 2 
(  4 5 7 9) 
(   6  10 12) 
( 2 4 6 8) 
(1 2 3 4) 

Wer einen Hinweis für mich hat

Answer 1

Eine einfache oder Sie können sagen Brute-Force-Ansatz, der mir in den Sinn kommt ist, sortieren t er kleine Mengen auf der Grundlage ihrer Größen, so dass nun unsere Bestellung wird in etwa so aussehen ->

(6,10,12), (1,3,7,8), (4,5,7,9), (2,4,6,8), (1,2,3,4), (3,5,9,12), (1,2,3,10,12) 

und es Gesamtgröße Zählung = 4 * 5 + 3 + 5 = 28 ist die Größe. So wie unsere jeder Teilmenge Größe sollte weniger als 9,

so Anzahl der Eimer Subsets required = 28/9 = 4.

So nehmen Sie jetzt 4 Eimer und beginnen kleine Sätze Einfügen ab i = 0 bis i = Länge, wobei Länge = Anzahl der kleinen Sätze.

Hoffe, das hilft!