Distribuição de recursos de provedores para o número máximo de receptores

Question

Considere há uma cidade com $ n $ residentes que precisam de internet e há $ m $ Provedores de Internet na cidade.Aqui na cidade todos os residentes precisam da Internet e todo residente sabe quais provedores estão disponíveis para ele.Formalmente deixe residente $ i $ tem lista de provedores $ a_i $ .Também cada provedor tem um número máximo de conexões que ele pode dar, ou seja, provedor $ i $ pode ter no máximo $ K_I$ conexões.Encontre a maneira ideal de fornecer à Internet para que o número de residentes cometido seja no máximo.

Meus pensamentos sobre a questão é que esta questão se parece com um derivativo do problema de embalagem de Knack com restrições, que sugere programação dinâmica, mas não consigo encontrar os estados.Alguém poderia me ajudar?

Answer 1

Este problema é um caso de problema máximo de fluxo .

Suponha que recebemos provedores da Internet $ p_1, p_2, \ cdozs, p_m $ e residentes $ r_1, r_2, \ CDOts, R_N $ . Considere uma rede de fluxo especificada como a seguinte.

Os nós
• são $ s, \ p_1, p_2, \ cdots, p_m, \ r_1, r_2, \ cdozs, r_n, \ t $ , onde $ S $ e $ t $ são dois nós extras de pé para a fonte e a pia.
• Há uma borda entre $ S $ e cada $ p_i $ com capacidade $ k_i $ .
• há uma borda entre $ P_I $ e $ r_j $ com capacidade 1 se $ P_I $ pode fornecer internet para $ r_j $ .
• Há uma borda entre cada $ r_j $ e $ t $ com capacidade 1.

O que queremos é encontrar o fluxo máximo de $ s $ para $ t $ . < / p >.

Existem muitos algoritmos para resolver um problema máximo de fluxo no tempo polinomial. Por exemplo, algoritmo Ford-Fulkerson e O algoritmo Díntico são muito populares. O código-fonte que implementa esses algoritmos em várias linguagens de programação pode ser encontrado facilmente.

Todos esses algoritmo produzirão um fluxo máximo integral, então não nos preocuparemos caso o fluxo máximo computado estipule que algum provedor deve fornecer 0,42 ou $ \ frac {\ sqrt2} 2 $ Internet para algum residente. Você pode verificar o teorema do fluxo integral .