Dato k set, ognuno contiene diversi elementi.
Voglio dividerli in due gruppi,
il primo gruppo contiene m set, il secondo gruppo contiene n set, m + n = k.
Sia w1 la somma dei pesi di tutti gli elementi nell'unione del primo gruppo di insiemi.
e w2 sono la somma dei pesi di tutti gli elementi nell'unione del secondo gruppo di insiemi.
Disegna un algoritmo per suddividere i k set in due gruppi in modo che w1 * m + w2 * n abbia il valore minimo.
Algoritmo 1:
Imposta il primo gruppo vuoto, quindi continua a fare queste operazioni: muoversi in un set dal gruppo due al gruppo uno; spostando un set dal gruppo 1 al gruppo 2; o passare due serie nei due gruppi; ogni passaggio non deve aumentare il valore w1 * m + w2 * n finché non è possibile eseguire altre operazioni. Non funziona, posso facilmente trovare dei controesempi quando questo algoritmo si arresta, il valore non è minimo.
Algoritmo 2:
Per prima cosa dividiamo i k set in k gruppi, ognuno contiene un set. Quindi, dividi i gruppi k in gruppi k-1 in modo che il valore Σw m sia minimo, ora i due gruppi nello stesso gruppo, consideriamo che sono sempre nello stesso gruppo, quindi dividi i gruppi k-1 in gruppi k-2 in modo che il valore Σw m sia minimo ... finché non abbiamo solo due gruppi. Non funziona, posso facilmente trovare controesempi.