Какой алгоритм это? Лучший способ распространения ограниченных ресурсов

Question

Я недавно увидел этот вопрос в задаче программирования, и я хотел бы знать, какой известный алгоритм CS это напоминает. Я реализовал грубое решение. Я знаю, что должен быть лучший способ сделать это, но я не уверен в том, что нужно искать. Это кажется как вариация проблемы с рюкзаком ... но есть достаточно различий, что я немного тупик.

Проблема:

Есть 3 города (A, B, C), с населением (100, 100, 200). Вы можете построить 4 больницы. Постройте больницы, чтобы вы минимизировали количество людей, посещающих каждый.

В этом примере ответом будет: построить 1 в A, 1 в B и 2 в C. Это означает, что каждая больница обслуживает 100 человек (оптимальное решение).

Если вы должны были распространять больницы как 1 в A, 2 в B и 1 на C, например, вы бы усреднили (100, 50, 200), что дает вам худший случай 200 (не Оптимальное решение).

Спасибо.

Добавление:

• Чтобы упростить проблему, # больниц всегда будет >= # городов. В каждом городе должно быть не менее 1 больницы.

Answer 1

1. Назначить больницу для каждого города
2. Хотя больницы оставили
3. Отработать населения соотношение больницы для каждого города
4. Присвоить больницу на один с самым высоким соотношением
5. Loop

Answer 2

Эта проблема может быть решена путем использования бинарного поиска. Поэтому мы ищем минимальное количество людей, обслуживаемых больницей.

псевдокоде:

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; 

Временная сложность будет O (п войти м) с п является номером города и м в общей численности населения.

Answer 3

Это пример проблемы, которая может быть решена с помощью динамического программирования. Следующие работы java code решает эту проблему в O (M * N^2) время, когда
М = ​​Количество городов и
N = Общее количество больниц

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; 
    } 

Штаты будут (я, п), где i представляет i-й город, а n представляет количество доступных больниц. Он представляет собой максимальное количество людей, которые будут посещать больницу для лучшего распределения российских больниц от i-го города до конца. Таким образом, ответ будет для состояния (0, 4) для примера, который у вас есть в вашем вопросе.

Так что теперь в каждом городе вы можете разместить максимум из

maxHospitals = п-remainingCities больницы, где
remainingCities = totalCities-я-1.

Итак, начните с размещения как минимум 1 больницы в этом городе до максимума, а затем повторите попытку для других мелких проблем.

Количество состояний = O (M * N^2)
Время на состояние = O (1)

Поэтому сложность Time = O (M * N^2)