c++ - metodo - Algoritmo para determinar la diversión máxima
metodo sort en c++ (2)
Debería elegir la opción divertida, a menos que ponga a Bessie por encima del umbral de la enfermedad. ¿Hay una mejor manera de hacer eso?
El problema es que no estás maximizando la diversión aquí, solo estás evitando que Bessie se enferme. Cuando llegas a una sección que la pondría por encima del límite mareado, puedes agregar más diversión al retroceder y tomar la opción de no diversión en alguna sección anterior. Digamos que tienes una entrada como esta, en orden FD:
1 400
5 450
10 25
18 75
20 400
Además, digamos que ya está cerca del límite de vértigo cuando llega a la primera sección de arriba. Podría tomar la opción de diversión en las dos primeras secciones y obtener un aumento de F de 6 y un aumento de D de 850. Tal vez eso lo pone justo en el límite. Ahora no tiene más remedio que tomar la opción no divertida para las siguientes secciones. Por otro lado, si elige la opción no divertida para las primeras dos secciones, puede elegir la opción divertida para las siguientes tres y obtener un aumento de F de 48 para un aumento de D de solo 500.
Su algoritmo actual toma la opción divertida si la proporción F: D es mayor que 1 y le queda suficiente capacidad de mareo. Eso es razonable, pero no óptimo. Es probable que ninguna relación fija dé una solución óptima. En su lugar, debe considerar el beneficio y el costo de cada opción para cada sección.
El problema en sí se puede encontrar here . La esencia de esto es que Bessie está montando una montaña rusa, pero se siente mareada. ¿Cuál es la cantidad máxima de diversión que puede tener sin sobrepasar su "límite de vértigo"? La entrada consiste en:
" NKL
donde N (1 ≤ N ≤ 1,000) es el número de secciones en este particular la montaña rusa; K (1 ≤ K ≤ 500) es la cantidad que bajará el nivel de mareo de Bessies si mantiene los ojos cerrados en cualquier sección del viaje; y L (1 ≤ L ≤ 300,000) es el límite de mareo que Bessie puede tolerar; si su mareo se vuelve más grande que L, Bessie se enfermará, ¡y eso no es divertido!
Cada una de las siguientes N líneas tendrá dos enteros:
FD
donde F (1 ≤ F ≤ 20) es el aumento en la diversión total de Bessies que obtiene Shell si mantiene los ojos abiertos en esa sección, y D (1 ≤ D ≤ 500) es el aumento a su nivel de mareo si mantiene sus ojos abierto en esa sección. Las secciones se enumerarán en orden ".
Mi algoritmo para resolver esto se ve así:
cin >> N; // sections
cin >> K; // amount dizziness can go down
cin >> L; // dizzy ceiling
belowL = L; // sets the amount of dizzy left
for (int i = 0; i < N; i++) {
cout << "/n" << i;
cin >> F >> D; // fun increase and dizzy increase
if (D < belowL) {
if (F >= D) {
funTotal += F;
}
}
else {
belowL -= K;
}
Sin embargo, esto no siempre da el resultado correcto. ¿Cuál es el problema? Debería elegir la opción divertida, a menos que ponga a Bessie por encima del umbral de la enfermedad. ¿Hay una mejor manera de hacer eso?
Entonces, en lugar de darle un código, aquí hay una explicación de la solución del problema.
El enfoque básico es resolver usando la programación dinámica, ya que esto se reduce a lo que se llama un problema de mochila . Piénselo de esta manera, su mareo es lo mucho que puede cargar en el saco a la vez y la diversión es lo que le gustaría maximizar (en comparación con decir el valor de los "artículos" que lleva en un saco). Ahora, lo que nos gustaría hacer es disfrutar al máximo de la montaña rusa (el mayor valor en el saco) sin que se maree demasiado (sobrepasar el límite de "peso" del saco).
Así que ahora desea elegir qué partes tiene los ojos abiertos / cerrados (ya sea que un artículo esté en el saco o no). Así que una manera fácil de pensar en esto es elegir el máximo de ambas opciones. Si puede mantener los ojos abiertos sin sobrepasar el umbral o si solo tiene que mantener los ojos cerrados. Pero ahora el problema cambia, verás si ella mantiene los ojos abiertos, su umbral de mareo disminuirá (más fácil de resolver problemas secundarios).
Con esta información, resulta fácil adaptar la solución de mochila a este problema sin tener que utilizar el retroceso o la recursión.
La idea es guardar todos los subproblemas resueltos previamente en una matriz para que pueda reutilizar los resultados en lugar de recalcularlos cada vez. Tenga en cuenta que un truco que puede usar es que solo necesita la fila actual de la matriz y la que se resolvió anteriormente porque la relación de recurrencia para la mochila solo requiere esas entradas :)
PS Estaba en la región donde se dio este problema y lo resolví, es bueno ver este problema de nuevo