这是什么算法？分配有限资源的最佳方式

Question

最近在一个编程挑战赛上看到这道题，想知道这道题类似于哪个著名的CS算法。我实施了一个粗略的解决方案。我知道一定有更好的方法来做到这一点，但我不确定要搜索的术语。它似乎像是背包问题的一个变体...但是有足够多的差异让我有点困惑。

问题：

有 3 个城市（A、B、C）的人口为（100、100、200）。您可以建造 4 家医院。建造医院，以便最大限度地减少每家医院的就诊人数。

在这个例子中，答案是：在 A 中建造 1 个，在 B 中建造 1 个，在 C 中建造 2 个。这意味着每家医院服务 100 人（最优解）。

例如，如果您将医院分配为 A 中的 1 家、B 中的 2 家和 C 中的 1 家，您将取平均值 (100, 50, 200)，这样最坏的情况是 200（不是最优解）。

谢谢。

附录：

为简化问题，医院的数量将始终是 >= 城市的数量。每个城市应该至少有1家医院。

Answer 1

给每个城市分配一个医院
医院离开时
计算每个城市的人口与医院比率
将医院分配给比例最高的医院
循环

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(n log m) 其中 n 是城市数量，m 是总人口。

Answer 3

这是一个可以使用动态规划求解的问题示例。以下工作 java code 在 O(M * N^2) 时间内解决了这个问题，其中
M = 城市数量，
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, n)，其中 i 代表第 i 个城市，n 代表可用医院的数量。它表示从第 i 个城市开始到最后，为了 n 个医院的最佳分配，可能会去任何一家医院就诊的最大人数。因此，对于问题中的示例，答案将是状态 (0, 4)。

现在每个城市最多可以放置

maxHospitals = n-remainingCities 家医院，其中
剩余城市 = totalCities-i-1。

因此，首先在该城市放置至少 1 家医院，直到 maxHospitals，然后再重复其他较小的子问题。

状态数 = O(M * N^2)
每个状态的时间 = O(1)

因此，时间复杂度 = O(M * N^2)

这是什么算法？分配有限资源的最佳方式

What algorithm is this? Best way to distribute limited resources

algorithm

computer-science