programming - goodrich tamassia data structures and algorithms in java 5th edition pdf

Seleccionar una combinación de costo mínimo

Question

Tengo datos de diferentes artículos en diferentes restaurantes

 Rest Item Price
----------------------
ABC dosa 14
ABC idly 30
ABC idly+upma 25
123 dosa 30
123 idly 7
123 upma 12
XYZ dosa 20
XYZ idly 12
XYZ upma 20
XYZ dosa+upma 30
XYZ dosa+idly+upma 40

Now I need to pickup a restaurant which gives me the best deal of "dosa+idly+upma" items.

Del ejemplo anterior: será el restaurante "ABC"

¿No puedo diseñar una forma eficiente de hacer esto o no tener idea de cómo hacerlo? ¿Alguna idea?

Actualizar

Aquí cómo se ven mis objetos

Class Rest{
Map<String,Integer> menu; //item,price map
}

Answer 1

1. Calcule las posibles combinaciones de precios: itere a través del mapa y analice las cadenas. Almacene cada combinación de precios.

2. Filtra los precios más caros.

3. Compare los precios restantes en cada restaurante y devuelva el restaurante con el precio más barato.

También podría hacer algunas comprobaciones para minimizar las iteraciones, por ejemplo:

• Si ociosamente es> que ocioso + umpa, no calcule las combinaciones que implican ociosamente.

Answer 2

Primero necesita hacer toda la combinación posible de 3 elementos correspondientes a diferentes restaurantes como:

XYZ dosa+idly+upma 52
XYZ dosa+upma+idly 42
XYZ dosa+idly+upma 40

Lo mismo el caso anterior con todos los restaurantes.

Luego, clasifique el precio y deje que el precio mínimo sea WIN.

Answer 3

Un bosquejo de un posible algoritmo codicioso es:

1. Revise todas las ofertas únicas (por ejemplo, dosa , inactivo o upma ) para encontrar el mínimo de cada una.
2. Revise todas las ofertas de binaray (por ejemplo, inactivo + upma ) / terciario (...), compare si es más barato que las ofertas únicas y reemplace si es así.

Deberá codificar la oferta deparsing aún, pero no debería ser tan difícil. Este algoritmo encontrará buena, pero no necesaria, la mejor solución, y podría funcionar en smaples muy pequeños.

En realidad, su problema se compara con los problemas de la mochila o TSP, que son NP-completos y, por lo tanto, solo pueden resolverse en tiempo exponencialmente. Si desea una solución para eso, considere leer muchos documentos y codificar aún más. Ese es el santo grial de la informática. ;-)

ACTUALIZACIÓN: A petición del TO, aquí hay un bosquejo de pseudocódigo exponencial:

foreach restaurant
create a list of all possible combinations of the offers // here''s the exp!
filter those combinations that hold more/less than 1 dosy/idly/umpa
select minimum of the remaining ones

Comentario: ¡Esto es realmente feo, cariño! :-(

Answer 4

tratar

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Mult {
/**
* @param args
*/
public static void main(String[] args) {
Map<String,List<X>> xx = new HashMap<String,List<X>>();
xx.put("ABC",new ArrayList<X>());
xx.get("ABC").add(new X("", 0));
xx.get("ABC").add(new X("dosa", 14));
xx.get("ABC").add(new X("idly", 30));
xx.get("ABC").add(new X("idly+upma", 25));
xx.put("123",new ArrayList<X>());
xx.get("123").add(new X("", 0));
xx.get("123").add(new X("dosa", 30));
xx.get("123").add(new X("idly", 7));
xx.get("123").add(new X("upma", 12));
xx.put("XYZ",new ArrayList<X>());
xx.get("XYZ").add(new X("", 0));
xx.get("XYZ").add(new X("dosa", 20));
xx.get("XYZ").add(new X("idly", 12));
xx.get("XYZ").add(new X("upma", 20));
xx.get("XYZ").add(new X("dosa+upma", 30));
xx.get("XYZ").add(new X("dosa+idly+upma", 40));
String[] t = {
"dosaidlyupma",
"idlydosaupma",
"upmaidlydosa",
"dosaupmaidly",
"upmadosaidly",
"idlyupmadosa"};
Set<String> targets = new HashSet<String>(Arrays.asList(t));
Map<String,Integer> best = new HashMap<String,Integer>();
for(String restaurant:xx.keySet()){
best.put(restaurant, Integer.MAX_VALUE);
String combo = null;
for(X a:xx.get(restaurant)){
int deal = a.price;
combo = a.item;
for(X b:xx.get(restaurant)){
deal = deal + b.price;
combo = combo + "+" + b.item;
for(X c:xx.get(restaurant)){
deal = deal + c.price;
combo = combo + "+" + c.item;
if (targets.contains(combo.replaceAll("//+", ""))){
// System.out.println(restaurant+"/t"+combo.replaceAll("//+", "")+"/t"+deal);
if (best.get(restaurant) > deal){
best.put(restaurant, deal);
}
}
}
}
}
}
System.out.println(best);
}
}

Te regalaré

{XYZ = 40, ABC = 39, 123 = 49}

es el viejo enfoque de la buena fuerza bruta.

no es el mejor, pero para este pequeño conjunto, funciona.

Answer 5

Este problema es NP-Hard . Mostraré una reducción del problema de cobertura del juego .

Establecer problema de cobertura (SCP):
Dado un universo de elementos U (en su ejemplo U={dosa,idly,upma} ) y un conjunto de subconjuntos de U , que sea S (por ejemplo S={{dosa}, {idly,upma}, {upma}} ) Encuentra el menor número de subconjuntos de S modo que su unión sea igual a U

La reducción:
Dado un problema de cobertura de conjuntos con U y S , cree una instancia de su problema con un restaurante, de modo que el precio de cada artículo en S (que es un conjunto de uno o más elementos) sea 1.

Ahora, dada una solución óptima a su problema, el precio mínimo posible, es básicamente el número mínimo de subconjuntos necesarios para cubrir el ''universo''.
Dada una solución óptima para el problema de cobertura del conjunto, la cantidad de conjuntos necesarios es el precio mínimo del subconjunto.

Conclusión:
Como hemos visto que resolver este problema de manera eficiente resolverá el SCP de manera eficiente, podemos concluir que el problema es NP-Hard, y por lo tanto no hay una solución polinómica conocida para él (y la mayoría cree que uno no existe).

Las alternativas están usando una solución heurística o una de fuerza bruta (solo busca todas las posibilidades, en tiempo exponencial).