What algorithm is this? Best way to distribute limited resources

Question

I recently saw this question on a programming challenge, and I'd like to know which well-known CS algorithm this resembles. I implemented a crude solution. I know there must be a better way to do it, but I'm not sure of the terms to search for. It seems like a variation of the knapsack problem... but there are enough differences that I'm a bit stumped.

Problem:

There are 3 cities (A, B, C) with populations (100, 100, 200). You can build 4 hospitals. Build the hospitals so that you minimize the # of people visiting each one.

In this example, the answer would be: build 1 in A, 1 in B, and 2 in C. This means that each hospital serves 100 people (optimal solution).

If you were to distribute the hospitals as 1 in A, 2 in B, and 1 in C, for example, you would average (100, 50, 200), which gives you a worst case of 200 (not the optimal solution).

Thanks.

Addendum:

• To simplify the problem, the # of hospitals will always be >= the # of cities. Every city should have at least 1 hospital.

Answer 1

1. Assign a hospital to each city
2. While hospitals left
3. Work out the the Population to Hospital ratio for each city
4. Assign a hospital to the one with the highest ratio
5. Loop

Answer 2

This problem can be solved by using binary search. So we search for the minimum number of people served by a hospital.

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;   

Time complexity will be O(n log m) with n is number of city and m is total population.

Answer 3

This is an example of a problem which can be solved using dynamic programming. The following working java code solves this problem in O(M * N^2) time where
M = Number of cities, and
N = Total number of hospitals

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

States will be (i, n) where i represents the i th city and n represents the number of hospitals available. It represents the maximum number of people that would be visiting any hospital for the best allocation of n hospitals from the i th city onwards to the end. So the answer would be for the state (0, 4) for the example you have in your question.

So now at each city you can place a maximum of

maxHospitals = n-remainingCities hospitals, where
remainingCities = totalCities-i-1.

So start by placing at least 1 hospital at that city upto maxHospitals and then recur for other smaller sub problems.

Number of states = O(M * N^2)
Time per state = O(1)

Therefore, Time complexity = O(M * N^2)