Três agendamento da cidade

Question

Eu me deparei com A seguinte questão da entrevista

.

Existem 2n pessoas que uma empresa está planejando entrevistar.O custo de voando a pessoa que a cidade a é custa [i] [0], e o custo de voando a pessoa para a cidade B é custa [i] [1].

Retorna o custo mínimo para voar todas as pessoas para uma cidade de tal modo que exatamente n pessoas chegam em cada cidade.

A solução para isso envolve abordagem gananciosa, onde classificamos a matriz com base no parâmetro "lucro".O lucro de escolher a cidade A para um candidato i é definido como costs[i][1] - costs[i][0] e escolha os principais elementos da metade da matriz classificada para ir a um e descansar para b.

e se esta pergunta for modificada para 3 cidades e você encontrar uma partição ideal de n / 3 pedaços? O algoritmo ganancioso ainda funciona?

Answer 1

generalizando com $ KN $ pessoas e $ k $ cidades que podemos ver "Mover para a cidade $ J $ "como uma tarefa.Além disso, temos $ n $ cópias de cada tarefa.Para todas as cópias de uma tarefa $ j $ , o custo para pessoa $ i $ para passar para essa tarefaé $ c_ {i, j} $ .

Mas agora o problema é uma instância direta do problema de atribuição equilibrado , com complexidade $ o ((kn) ^ 3) $ .