这是什么算法？如何最好地分配有限的资源。

Question

最近我在一个编程挑战中看到了这个问题，想知道它与哪个著名的计算机科学算法类似。我实现了一个粗略的解决方案。我知道一定有更好的解决方法，但我不确定要搜索哪些术语。它似乎是背包问题的变种...但是存在足够的差异让我有点困惑。

问题：

有三个城市（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所医院。

- smg

---

每个城市都必须有医院吗？ - Nikunj Banka

@NikunjBanka 我澄清了问题（请参见：附录）。 - smg

有任何限制吗？最多有多少个医院和城市？人口数量呢？ - Pham Trung

这是一种退化的容量设施选址问题。贪心算法可以得到最优解。 - David Eisenstat

Answer 1

1. 为每个城市分配一家医院
2. 当还有剩余的医院时
3. 计算每个城市的人口医院比率
4. 为具有最高比率的城市分配一家医院
5. 进入循环

- Dijkgraaf

---

如果城市数量变得很大，请使用基于人口医院比率排名的最大堆实现PrioirtyQueue来维护性能。性能应为**O(N log M)**，其中N =医院数量，M是城市数量。 - Pieter Geerkens

“(城市内医院数) = floor((城市人口) / (所有城市人口总和) * (医院数量)) - 1” 这个公式作为算法起始值的下限是否合适？而且，也许不需要减去“-1”。 - Nuclearman

@Nuclearman，一开始我也是这么想的，但实际上并不是这样。考虑一个有100万人口的大城市和几个规模为2的小城市，总共需要分配1000家医院。我们宁愿从大城市中取出比下限更多的医院，以确保每个小城市都有2家医院。 - David Eisenstat

@DavidEisenstat：啊，是的，确实有这个问题。但仍然觉得应该有比逐个分配医院更好的方法。与其将其视为下限，不如将其视为起点，然后使用上述方法确定哪些城市拥有过多的医院并重新分配。似乎这种方法需要重新分配的医院要少得多，而不是按照此答案分配的数量。虽然这似乎接近Pham Trung的答案所追求的。 - Nuclearman

太棒了。这个简单的方法非常有效。看起来我一直试图将其转化为背包问题的版本，把事情复杂化了。这里有一个上述算法的工作示例：https://dotnetfiddle.net/IuGW4h - smg

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是总人口。

- Pham Trung

Answer 3

这是一个可以使用动态规划解决的问题示例。以下有效的Java代码可以在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)。

因此，在每个城市，您可以最多放置n-remainingCities个医院，其中remainingCities = totalCities-i-1。因此，请从该城市至少放置1个医院，直到maxHospitals，并针对其他较小的子问题进行递归。

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

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

- Nikunj Banka