Algoritmo para determinar la diversión máxima

El problema en sí se puede encontrar en here. La esencia de esto es que Bessie está montando una montaña rusa, pero se marea. ¿Cuál es la cantidad máxima de diversión que puede tener sin superar su "límite vertiginoso"? La entrada consiste en:Algoritmo para determinar la diversión máxima

"NKL

donde N (1 ≤ N ≤ 1000) es el número de secciones en este particular, la montaña rusa; K (1 ≤ K ≤ 500) es la cantidad el nivel de mareos de Bessies disminuirá 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 llega a ser mayor que L, Bessie lo hará. enfermarse, y eso no es divertido!

Cada una de las siguientes N líneas tendrá dos enteros:

donde F (1 ≤ M ≤ 20) es el aumento de total diversión Bessies que Shell conseguir si mantiene los ojos abiertos en esa sección, y D (1 ≤ D ≤ 500) es el aumento a su nivel de mareo si mantiene los ojos abiertos en esa sección. Las secciones se enumeran en orden "

Mi algoritmo para resolver esto se parece a esto:..?

 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 producir el resultado correcto ¿Cuál es el problema que debe recoger la opción de diversión, a menos que pondría Bessie por encima del umbral enfermedad. ¿hay una mejor manera de hacer eso?

Fuente

2012-02-15 Linell

Tengo curiosidad por saber por qué alguien votó para cerrar esto, está bastante bien redactado y también tiene un enlace al problema original. : p No tengo tiempo para leerlo, pero si lo hice parece un problema divertido. –

Deberías buscar el enfoque que maximiza la diversión total, pero actualmente solo intentas divertirte lo más pronto posible. –

Me recuerda a [RollerCoaster Tycoon] (http://en.wikipedia.org/wiki/Roller_Coaster_Tycoon). Me encanta cuando los invitados bajan de la montaña rusa y vomitan en la acera. –

Así que en lugar de darle el código aquí hay una especie de explicación de la solución al problema.

El enfoque básico es resolver usando programación dinámica, ya que esto se reduce a lo que se llama Knapsack problem.Piénselo de esta manera, su mareo es cuánto puede llevar en el saco de inmediato 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 (la mayor parte del valor en el saco) sin marearla demasiado (sobrepasando el límite de "peso" en el saco).

Así que ahora usted quiere elegir qué partes tiene los ojos abiertos/cerrados (si un artículo está en el saco o no). Entonces, 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 mantener los ojos cerrados. Pero ahora el problema cambia, usted ve si mantiene los ojos abiertos su umbral de mareo disminuirá (más fácil para resolver problemas secundarios).

Al usar esta información, resulta fácil adaptar la solución de mochila a este problema sin tener que recurrir al retroceso ni a la recursión.

La idea es guardar todos los subproblemas resueltos previamente en una matriz para que pueda reutilizar los resultados en lugar de volver a calcularlos cada vez. Tenga en cuenta que un truco que puede usar es que solo necesita la fila actual de la matriz y la anterior porque la relación de recurrencia para la mochila solo requiere esas entradas :)

PD Estuve en el regional donde se dio este problema y lo resolvió, es bueno volver a ver este problema

Fuente

2012-02-15 20:34:13

se debe escoger la opción de diversión, a menos que pondría Bessie por encima del umbral enfermedad. ¿hay una mejor manera de hacer tha t?

El problema es que no estás maximizando la diversión aquí, solo estás impidiendo que Bessie se enferme. Cuando llegue a una sección que la pondría por encima del límite de vértigo, es posible que pueda agregar más diversión retrocediendo y tomando la opción no divertida en alguna sección previa. Digamos que tienes de entrada como esta, en fa fin D:

Además, vamos a decir que ella ya está cerca del límite de mareo cuando se llega a la primera sección de arriba. Podría tomar la opción divertida en las dos primeras secciones y obtener un aumento de F de 6 y un aumento de D de 850. Quizás eso la ponga en el límite. Ahora no tiene más remedio que tomar la opción no divertida para las secciones siguientes. Por otro lado, si toma la opción no divertida para las dos primeras secciones, puede tomar la opción divertida para las siguientes tres y obtener un aumento en F de 48 para un aumento D de solo 500.

Su el algoritmo actual toma la opción divertida si la relación F: D es mayor que 1 y usted tiene suficiente capacidad de mareo. Eso es razonable, pero no es óptimo. Es probable que ninguna relación fija proporcione una solución óptima. En cambio, debe considerar el beneficio y el costo de cada opción para cada sección.

Fuente

2012-02-15 20:31:28 Caleb

Algoritmo para determinar la diversión máxima

Respuesta

Cuestiones relacionadas