# Algorithm for cliques in weighted graph

Is there a known algorithm (besides brute force) for the following problem:

We have given an edge-weighted complete graph $$G$$ and a finite set of natural numbers $$A = \lbrace n_1,\ldots,n_k \rbrace$$ (to begin with we can just assume that $$A$$ has only one element). We want to decompose $$G$$ in cliques whose size is an element of $$A$$ and such that the sum of all edges of these cliques is maximal. (If this is not possible, e.g., in the case when $$A = \lbrace n \rbrace$$ and $$n$$ is not a divisor of the number of vertices of $$G$$, we are allowed to add vertices and edges (with weight $$0$$) to $$G$$.)

This is a modeling for the following problem: Given a group of people, a "friendship index" between each two people and a hotel with rooms of size $$n_1,\ldots,n_k$$, determine the optimal room division.

I have posted this question (some time ago) also at MathStackExchange, but without answer.

Suppose $$\Gamma$$ is the graph to be 3-edge-colored. Let $$L(\Gamma)$$ be the line graph of $$\Gamma$$. Let $$G$$ be the complete graph with order $$|L(\Gamma)|$$.
Assign the weights in $$G$$ as follows: $$-1$$ if the edge is in $$L(\Gamma)$$, and 0 otherwise. Let $$A= \lbrace {|\Gamma|/2} \rbrace$$.
Then $$L(\Gamma)$$ must be partitioned into 3 groups, and the largest sum, $$0$$, is attained iff the groups are all independent sets in $$L(\Gamma)$$, which gives a 3-edge coloring of $$\Gamma$$.