Procuro um desenvolvedor Python com expertise em otimização para desenvolver uma solução para uma variante do problema das múltiplas mochilas (Multiple Knapsack Problem - MKP). O desafio é criar um algoritmo que otimize a alocação de itens em várias mochilas, minimizando a discrepância do valor médio dos itens em cada mochila e garantindo que todos os itens sejam sempre alocados. A entrada para o algoritmo será um DataFrame com uma estrutura específica, e a saída será outro DataFrame detalhando a alocação dos itens.

Detalhes do Projeto:

Contexto do Problema:

Variação do clássico problema da mochila, adaptado para múltiplas mochilas, com o objetivo adicional de minimizar a variação do valor médio dos itens em cada mochila.
Restrição Crítica: Todos os itens devem ser alocados entre as mochilas sem exceção.
Requisitos Específicos:

Quantidade de Mochilas (y): Número variável.
Capacidades das Mochilas (x): Capacidade específica para cada mochila.
Itens (n): Cada item com um valor e peso associados, podendo existir itens iguais.
Formato de Entrada:

DataFrame com as colunas:
item: Identificador único.
nome_item: Descrição do item.
quantidade(peso): Representando o peso (sempre 1 neste caso).
valor: Valor do item.
quantidade*valor: Produto da quantidade pelo valor.
Saída Esperada:

O algoritmo deve gerar um DataFrame com a seguinte estrutura:
mochila: Identificador da mochila.
# item: Identificador do item alocado.
quantidade: Quantidade do item alocado (neste caso, sempre 1).
valor: Valor do item alocado.
Esta saída deve refletir a distribuição ótima dos itens pelas mochilas.
Desafios e Considerações:

Eficiência do algoritmo para lidar com diferentes quantidades de itens e mochilas.
Tratar casos onde a alocação ideal não é possível devido às restrições de capacidade.
Expectativas e Entregas:

Script Python bem documentado e testado.
Comentários detalhados no código.
Exemplos de uso com diferentes conjuntos de dados.