Tengo una lista de productos y necesito escribir un algoritmo que calcule un precio mínimo para el cliente.
Cada producto tiene su propio precio y hay un precio de grupo: el precio de varios productos juntos.
El algoritmo calculará qué grupos elegir para obtener un precio mínimo
Por ejemplo:
Supongamos que el cliente quiere comprar los productos c1,c2,c3,c4
los precios son: c1 =70$, c2 =70$, c3 =70$, c4 =70$.
Cuando los grupos son:
g1 = {c1, c2} = 120 $ g2 = {c3, c4} = 130 g3 = {c2, c3, c4} = 170
Las opciones son:
1. paga por cada producto por separado $70,= 280$
2. seleccione para comprar el grupo g1,g2= 250$
3. seleccione comprar grupo g3 + producto c1 por separado = 240$
puede haber más opciones, de todos modos - en este ejemplo el precio más asequible es la tercera opción, grupo g3+c1, 240$.
¿Qué algoritmo puede resolver el problema?
Revise todas las combinaciones de grupos posibles y descubra cuál es el precio mínimo y qué grupos usar.
Estoy seguro de que es un algoritmo familiar, una pregunta que existe en geeks para geeks , solo que no sé cómo configurarlo, cuál es su famoso nombre.
Establecer problema de portada - GeeksforGeeks:
public static int minCostCollection(final Set<Integer> unv, final Set<Integer>[] sets, final Map<Set, Integer> costs, final List<Set> list, final int pos) { if (unv.size() == 0) { int cost = 0; for (final Set s : list) { cost = cost + costs.get(s); } return cost; } if (pos < 0) { return Integer.MAX_VALUE; } final Set<Integer> unvCopy = new HashSet<>(unv); final List<Set> list1 = new ArrayList<>(list); list.add(sets[pos]); for (final Integer elem : sets[pos]) { unv.remove(elem); } final int cost1 = minCostCollection(unv, sets, costs, list, pos - 1); final int cost2 = minCostCollection(unvCopy, sets, costs, list1, pos - 1); return Math.min(cost1, cost2); } public static void main(final String[] args) { final Set<Integer> unv = new HashSet<>(); unv.add(1); unv.add(2); unv.add(3); unv.add(4); unv.add(5); final Set<Integer> s1 = new HashSet<>(); s1.add(4); s1.add(1); s1.add(3); final Set<Integer> s2 = new HashSet<>(); s2.add(2); s2.add(5); final Set<Integer> s3 = new HashSet<>(); s3.add(1); s3.add(4); s3.add(3); s3.add(2); final Set sets[] = {s1, s2, s3}; final Map<Set, Integer> costs = new HashMap<>(); costs.put(s1, 5); costs.put(s2, 10); costs.put(s3, 30); System.out.println(minCostCollection(unv, sets, costs, new ArrayList<Set>(), sets.length - 1)); }