hola chavales, no se bien si postear en DESARROLLO Y DISEÑO WEb, pero esq no sabía donde hacerlo.
os pido ayuda para programar lo siguiente:
En el juego del Pang tenemos a un explorador que tiene que usar una pistola con diferentes tipos de disparo para eliminar gradualmente B bolas de diferentes volúmenes V1, V2, …, VB. Cuando el disparo del jugador impacta contra una bola, dicha bola se divide en dos bolas de menor volumen. Existen n tipos de disparos que se van realizando de forma consecutiva y circular, de forma que cuando se ha realizado el n-ésimo disparo, el siguiente será igual al primero de la secuencia. Cada disparo divide la bola en 2 bolas repartiéndose el volumen entre las dos bolas según el tipo de disparo. La secuencia de disparos es la siguiente: {p1, p2, …, pn}, lo que quiere decir que para el disparo k comprendido entre 1 y n una bola de volumen V se divide en 2 bolas de volúmenes V1 = V * pk y V2 = V – V1. Cuando las bolas tienen el tamaño menor o igual a Vmin, si vuelven a ser disparadas, desaparecen.
El problema consiste en encontrar el mínimo número de disparos necesarios para conseguir eliminar todas las bolas.
Por ejemplo: Tenemos una bola (B=1) de volumen V1=4, siendo Vmin = 2, y tenemos 2 tipos de disparos: {1/4, 1/2}. La mejor solución serían 5 disparos.
Sin embargo, si el disparo 2 hubiera sido a la bola de volumen 1, habríamos tenido que hacer al menos 7 disparos (ya que la bola de volumen 3 se dividiría en 2 bolas de volúmenes 0,75 y 2,25 respectivamente).
Diseñe e implemente un algoritmo basado en Programación Dinámica que resuelva el problema del Pang.
Alguna idea? esq no se como colocar los estados para mi grafo, y como implementar este grafo.
gracias de antemano
