Thuật toán này là gì? Cách tốt nhất để phân phối tài nguyên giới hạn

Question

Gần đây tôi đã nhìn thấy câu hỏi này về một thách thức lập trình và tôi muốn biết thuật toán CS nổi tiếng nào giống như vậy. Tôi đã thực hiện một giải pháp thô. Tôi biết phải có một cách tốt hơn để làm điều đó, nhưng tôi không chắc chắn về các điều khoản để tìm kiếm. Nó có vẻ như giống như một biến thể của vấn đề ba lô ... nhưng có đủ sự khác biệt mà tôi là một chút bối rối.

Sự cố:

Có 3 thành phố (A, B, C) với dân số (100, 100, 200). Bạn có thể xây dựng 4 bệnh viện. Xây dựng các bệnh viện để bạn giảm thiểu số lượng người truy cập mỗi người.

Trong ví dụ này, câu trả lời sẽ là: xây dựng 1 trong A, 1 trong B và 2 trong C. Điều này có nghĩa là mỗi bệnh viện phục vụ 100 người (giải pháp tối ưu).

Nếu bạn phân phối các bệnh viện như 1 trong A, 2 trong B và 1 trong C, ví dụ, bạn sẽ trung bình (100, 50, 200), điều này mang lại cho bạn trường hợp xấu nhất là 200 (không phải là giải pháp tối ưu).

Cảm ơn.

Phụ Lục:

• Để đơn giản hóa vấn đề, cáC# của bệnh viện sẽ luôn luôn được >= # của thành phố. Mỗi thành phố nên có ít nhất 1 bệnh viện.

Answer 1

1. Gán một bệnh viện để mỗi thành phố
2. Trong khi các bệnh viện còn lại
3. làm việc ra các Dân số tỷ lệ bệnh viện cho mỗi thành phố
4. Gán một bệnh viện với một với tỷ lệ cao nhất
5. Vòng

Answer 2

Sự cố này có thể được giải quyết bằng cách sử dụng tìm kiếm nhị phân. Vì vậy, chúng tôi tìm kiếm số lượng người tối thiểu được phục vụ bởi bệnh viện.

Pseudo code:

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; 

Thời gian phức tạp sẽ O (n log m) với n là số thành phố và m là tổng dân số.

Answer 3

Đây là ví dụ về sự cố có thể được giải quyết bằng cách sử dụng lập trình động. Các hoạt động sau java code giải quyết vấn đề này trong thời gian O (M * N^2) thời gian nơi
M = Số các thành phố, và
N = Tổng số bệnh việ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; 
    } 

Kỳ sẽ là (i, n) trong đó i đại diện cho thành phố thứ i và n đại diện cho số lượng bệnh viện có sẵn. Nó đại diện cho số lượng người tối đa sẽ đến thăm bất kỳ bệnh viện nào để phân bổ tốt nhất các bệnh viện n từ thành phố thứ i trở đi đến cùng. Vì vậy, câu trả lời sẽ được cho nhà nước (0, 4) cho ví dụ bạn có trong câu hỏi của bạn.

Vì vậy, tại mỗi thành phố bạn có thể đặt tối đa là

maxHospitals = n-remainingCities bệnh viện, nơi
remainingCities = totalCities-i-1.

Vì vậy, hãy bắt đầu bằng cách đặt ít nhất 1 bệnh viện tại thành phố đó lên tối đa Bệnh viện và sau đó tái phát các vấn đề phụ nhỏ hơn khác.

Số bang = O (M * N^2)
Thời gian mỗi state = O (1)

Do đó, Thời gian phức tạp = O (M * N^2)