Che algoritmo è questo? Il modo migliore per distribuire risorse limitate

Question

Recentemente ho visto questa domanda su una sfida di programmazione, e mi piacerebbe sapere quale algoritmo CS noto questo assomiglia. Ho implementato una soluzione grezza. So che ci deve essere un modo migliore per farlo, ma non sono sicuro dei termini da cercare. È sembra come una variazione del problema dello zaino ... ma ci sono abbastanza differenze che sono un po 'perplesso.

Problema:

ci sono 3 città (A, B, C) con le popolazioni (100, 100, 200). Puoi costruire 4 ospedali. Costruisci gli ospedali in modo da ridurre al minimo il numero di persone che visitano ciascuno di essi.

In questo esempio, la risposta sarebbe: build 1 in A, 1 in B e 2 in C. Questo significa che ogni ospedale serve 100 persone (soluzione ottimale).

Se dovessi distribuire gli ospedali come 1 in A, 2 in B e 1 in C, ad esempio, avresti una media (100, 50, 200), che ti dà il caso peggiore di 200 (non il soluzione ottimale).

Grazie.

Addendum:

• per semplificare il problema, il # degli ospedali sarà sempre >= il # delle città. Ogni città dovrebbe avere almeno 1 ospedale.

Answer 1

1. Assegnare un ospedale per ogni città
2. Mentre gli ospedali lasciati
3. elaborare la Popolazione rapporto Hospital per ogni città
4. Assegnare un ospedale a quello con il più alto rapporto
5. Loop

Answer 2

Questo problema può essere risolto utilizzando la ricerca binaria. Quindi cerchiamo il numero minimo di persone servite da un ospedale.

pseudo codice:

int start = 0; 
int end =//total population 
while(start <= end) 
    int mid = (start + end)/2; 
    for(each city) 
     Calculate the number of hospital needed to achieve mid = (population/mid) 
    if(total of number of hospital needed <= number of available hospital) 
     decrease end; 
    else 
     increase start; 

Tempo complessità sarà O (n log m) con n è il numero di città ed m è la popolazione totale.

Answer 3

Questo è un esempio di un problema che può essere risolto utilizzando la programmazione dinamica. Il java code seguente lavoro risolve questo problema in O (M * N^2) il tempo in cui
M = Numero di città, e
N = numero totale di ospedali

public void run(){ 
     arr[0] = 100; 
     arr[1] = 100; 
     arr[2] = 200; 
     System.out.println(minCost(0, 4)); 
     printBestAllocation(0, 4, minCost(0, 4)); 
    } 

    static HashMap<String, Integer> map = new HashMap<String, Integer>(); 

    // prints the allocation of hospitals from the ith city onwards when there are n hospitals and the answer for this subproblem is 'ans' 
    static void printBestAllocation(int i, int n, int ans){ 
     if(i>=arr.length){ 
      return; 
     } 
     if(n<=0){ 
      throw new RuntimeException(); 
     } 

     int remainingCities = arr.length - i - 1; 
     for(int place=1; place<=n-remainingCities; place++){ 
      if(arr[i] % place == 0){ 
       int ppl = Math.max(arr[i]/place, minCost(i+1, n-place)); 
       if(ppl == ans){ 

        System.out.print(place + " "); 
        printBestAllocation(i+1, n-place, minCost(i+1, n-place)); 
        return; 
       } 
      }else{ 
       int ppl = Math.max(arr[i]/place + 1, minCost(i+1, n-place)); 
       if(ppl==ans){ 
        System.out.print(place + " "); 
        printBestAllocation(i+1, n-place, minCost(i+1, n-place)); 
        return; 
       } 
      } 
     } 
     throw new RuntimeException("Buggy code. If this exception is raised"); 
    } 

    // Returns the maximum number of people that will be visiting a hospital for the best allocation of n hospitals from the ith city onwards. 
    static int minCost(int i, int n){ 
     if(i>=arr.length){ 
      return 0; 
     } 
     if(n<=0){ 
      throw new RuntimeException(); 
     } 
     String s = i + " " + n; 
     if(map.containsKey(s)){ 
      return map.get(s); 
     } 
     int remainingCities = arr.length - i - 1; 
     int best = Integer.MAX_VALUE; 
     for(int place=1; place<=n-remainingCities; place++){ 
      int ppl; 
      if(arr[i] % place==0){ 
       ppl = Math.max(arr[i]/place, minCost(i+1, n-place)); 
      }else{ 
       ppl = Math.max(arr[i]/place + 1, minCost(i+1, n-place)); 
      } 
      best = Math.min(best, ppl); 
     } 
     map.put(s, best); 
     return best; 
    } 

Uniti saranno (i, n), dove Io rappresento la città e n rappresenta il numero di ospedali disponibili. Rappresenta il numero massimo di persone che visiterebbero un ospedale per la migliore assegnazione di n ospedali dalla città in poi alla fine. Quindi la risposta sarebbe per lo stato (0, 4) per l'esempio che hai nella tua domanda.

Così ora ad ogni città è possibile inserire un massimo di

maxHospitals = N-remainingCities ospedali, dove
remainingCities = totalCities-i-1.

Quindi iniziare collocando almeno 1 ospedale in quella città fino a max ospedali e quindi ricorrere per altri sub piccoli problemi.

Numero di stati = O (M * N^2)
Tempo per lo stato = O (1)

Pertanto, Tempo complessità = O (M * N^2)