什么算法是什么？分配有限的资源，最好的方法 [英] What algorithm is this? Best way to distribute limited resources

问题描述

我最近看到的一个编程挑战这个问题，我想知道哪些著名的CS算法此类似。我实现了一个粗糙的解决方案。我知道必须有一个更好的方式来做到这一点，但我不知道的术语来搜索。它的似乎的类似背包问题的变化......但也有足够的差异，我感到有点为难。

问题：

有3个城市（A，B，C），人口（100，100，200）。你可以建立4家医院。构建医院，让你最大限度地减少人员互访一个＃。

在这个例子中，答案是：建立1 A，1 B和2 C.这意味着每家医院提供100人（最佳解决方案）

如果你要分发医院为1 A，2 B和1℃，例如，你会平均水平（100，50，200），它给你的200最坏的情况（不是最佳溶液）。

感谢。

附录：

• 要简化问题，医院的＃永远是＆GT;城市= 的＃。每个城市都应该有至少1医院。

解决方案

1. 在指定一家医院为每个城市
2. 在医院留
3. 工作了人口向医院比每个城市
4. 在指定医院对具有最高比值
5. 循环

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.

解决方案

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

这篇关于什么算法是什么？分配有限的资源，最好的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！