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).