J'ai récemment vu cette question sur un défi de programmation et j'aimerais savoir quel algorithme CS bien connu cela ressemble. J'ai mis en place une solution brute. Je sais qu'il doit y avoir une meilleure façon de le faire, mais je ne suis pas sûr des termes de la recherche. Il semble comme une variation du problème du sac à dos ... mais il y a suffisamment de différences que je suis un peu souples.
problème:
Il y a 3 villes (A, B, C) avec des populations (100, 100, 200). Vous pouvez construire 4 hôpitaux. Construisez les hôpitaux afin que vous minimisez le nombre de personnes qui visitent chacun.
Dans cet exemple, la réponse serait: Build 1 dans A, 1 en B et 2 en C. Cela signifie que chaque hôpital sert 100 personnes (solution optimale).
Si vous deviez distribuer les hôpitaux comme 1 dans A, 2 en B et 1 en C, par exemple, vous auriez la moyenne (100, 50, 200), ce qui vous donne un pire cas de 200 (et non l'optimal solution).
Merci.
addendum:
> = le nombre de villes. Chaque ville devrait avoir au moins 1 hôpital.
3 Réponses :
Si le nombre de villes devient importante, utilisez une mise en œuvre maximale de ProiirTyQueue, classée sur le ratio population à hospitalier afin de maintenir la performance. Les performances doivent être O (n log m) où n = nombre d'hôpitaux et m est le nombre de villes.
Ne (hôpitaux en ville) = étage ((population de la ville) / (nombre total de villes) * (nombre d'hôpitaux)) - 1 fournir une limite inférieure appropriée à partir de laquelle cet algorithme peut commencer à ? En outre, le -1 ne peut pas être nécessaire.
@Nuclearman C'est ce que je pensais au début, mais ce n'est pas le cas. Considérons une grande ville, avec 1 000 000 personnes et plusieurs villes de la taille 2, avec une population - 1 000 hôpitaux à distribuer. Nous préférerions prendre plusieurs autres que la limite inférieure de la grande ville pour vous assurer que chaque petite ville dispose de 2 hôpitaux.
@Davideisenstat: ah oui il y a ça. On dirait toujours qu'il devrait y avoir une meilleure façon de distribuer des hôpitaux un par un. Plutôt que d'une limite inférieure, il serait peut-être préférable de le traiter comme un point de départ, puis utilisez l'approche ci-dessus pour déterminer où les villes ont trop d'hôpitaux et réaffectant. On dirait que cette approche devrait réaffecter beaucoup moins d'hôpitaux que ce ne serait attribué par cette réponse. Bien que cela semble proche de la réponse de Pham Trung.
Impressionnant. Cette méthode simple fonctionne bien. On dirait que je complique tout en essayant de le transformer en une version du problème du sac à dos. Voici un exemple de travail de l'algorithme ci-dessus: DotNetFiddle.net/iugw4h
Ce problème peut être résolu à l'aide de la recherche binaire. Nous recherchons donc le nombre minimum de personnes desservies par un hôpital.
pseudo code: la complexité du temps sera o (n log m) avec n est le nombre de ville et m est la population totale.
Ceci est un exemple de problème qui peut être résolu à l'aide de la programmation dynamique. Le travail suivant fonctionne code Java résout ce problème dans O (m * n ^ 2) heure d'où m = nombre des villes et
N = nombre total d'hôpitaux
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;
}
Chaque ville doit avoir un hôpital?
@Nikunjbanka j'ai clarifié le problème (voir: addendum).
Des contraintes? maximum combien d'hôpitaux et de villes? populations?
C'est une sorte de problème de localisation de l'installation capable de dégénération. L'algorithme gourmand renvoie des solutions optimales.