Este problema es NP-Hard , con una reducción de Knapsack-Problem .

Breve "prueba" intuitiva: la idea es crear un vértice para cada elemento: puede "tomarlo" o "no tomarlo" eligiendo el vértice con el costo o el vértice "gratis".

Bosquejo:

En lo anterior, puede ver, desde el Problema de la mochila, crear un gráfico, para cada artículo, puede elegir tomarlo, y pagar el costo y obtener el "valor", o ignorarlo.

Más formalmente:

Dada una instancia de mochila con weights=w1,w2,w3,...cn y cost=c1,c2,..,cn , con algún peso máximo W , cree un gráfico G=(V,E) con

 V= { V_i,U_i,W_i | i=0,...n } E= { (W_i,V_i+1,U_i+1 | i=0,...,n-1} U {(V_i,W_i+1), (U_i,W_i+1) | i=0,...,n-1 } value(W_i,V_i+1) = c_i+1 money(W_i,V_i+1) = w_i+1 value(W_i,U_i+1) = 0 money(W_i,U_i+1) = 0 money(V_i,W_i+1) = cost(V_i,W_i+1) = money(U_i,W_i+1) = cost(U_i,W_i+1) = 0

La solución a este problema que utiliza como máximo W dinero, será también la solución para mochilas con capacidad máxima de W.

Una posible solución de pseudopolinomio podría ser (usando la técnica de Programación Dinámica ):

 D(start,0) = 0 D(v,x) = infinity x < 0 D(v,x) = min { D(u,x-money(u,v)) + value(u,v) | for each edge (u,v) } U {infinity}

En lo anterior D(v,x) es la distancia mínima necesaria para viajar desde el nodo de inicio hasta v , pagando exactamente x dinero.

Tenga en cuenta que se puede hacer porque es un DAG, por lo que puede calcular los valores del primero al último según el tipo topológico del gráfico.

Cuando termine, debe buscar todos los valores de x desde 0 hasta MAXIMAL_AMOUNT_OF_MONEY_ALLOWED para encontrar el valor mínimo de D(target,x) , y esa es la respuesta.
Encontrar el costo real se hace volviendo sobre sus pasos, como se hace en otras soluciones de programación dinámica .

El tiempo de ejecución anterior es O(|V|*MAX_MONEY + |E|)

Usar algoritmo de inundación. Normas:
En cada nodo visitado, actualice una matriz de rutas y sus precios.
Libere la matriz cuando el nodo visitado ya no sea necesario.
Siempre elimine las rutas con precio> dinero.
Inicie la inundación en el nodo de origen.
Finalice la inundación en el nodo de destino cuando se inunden todos los bordes entrantes.
Siga la inundación usando bordes salientes cuando todos los bordes entrantes están inundados.
Al final, tome la ruta con el precio más alto en el nodo de destino.

Dado que su pregunta no se trata de encontrar una ruta en general y solo de encontrar una ruta dentro de un cierto costo, supondré que ya tiene algún algoritmo para encontrar la ruta más corta y hablaré en general sobre cómo modificarlo.

La forma más sencilla sería simplemente ignorar las rutas que aumentan el costo más allá de la cantidad que desea gastar. En su algoritmo de búsqueda de rutas, cuando agrega un borde a una ruta, abandone esa ruta si el costo total ahora es demasiado alto. Si es razonable omitirlo o marcarlo como no válido de alguna manera en su código, hágalo; de lo contrario, podría tratar el peso de la suma para la ruta como infinito, entonces se manejará solo.

Suponiendo que tiene alguna función para verificar el siguiente borde a lo largo de la ruta (y si no la tiene, o no está en este formato, simplemente adáptela a lo que tiene) ...

 // accepts the edge you are checking, max cost, and the sum weight and cost so far to this point // returns float array {sum cost, sum weight), or infinity if cost is exceeded void checkNextStep(Edge* edge, float maxCost, float* sumWeight, float* sumCost) { if(*sumCost + edge->cost > maxCost) { *sumWeight = INFINITY; *sumCost += edge->cost; } *sumWeight += edge->weight; *sumCost += edge->cost; }

Ahora, esa ruta se rechazará automáticamente si el costo supera su umbral, porque es probable que el infinito no sea la ruta más corta.

Si termina obteniendo una ruta más corta con peso infinito, eso significa que no tiene suficiente dinero para llegar a su nodo de destino, por ninguna ruta. Así que puedes usar eso como un cheque de que no puedes llegar allí en absoluto con tu sistema monetario.