I have list of products, and need to write an algorithm that will calculate a minimal price to the customer.
Each product has its own price, and there is a group price - the price of several products together.
The algorithm will calculate which groups to choose to get a minimum price
For example:
Suppose the customer wants to purchase the products c1,c2,c3,c4
the prices are: c1=70$, c2=70$, c3=70$, c4=70$.
When the groups are:
g1 = {c1, c2} = 120 $ g2 = {c3, c4} = 130 g3 = {c2, c3, c4} = 170
The options are:
1. pay for each product separately $ 70,= 280$
2. select to buy group g1,g2= 250$
3. select to buy group g3 + product c1 separately = 240$
may be there are more options, anyway - in this example the most affordable price is the third option, group g3+c1, 240$.
What algorithm can solve the problem?
Go through all the possible groups combinations, and find out what the minimum price is and which groups to use.
I'm sure it's a familiar algorithm, A question that exists in geeks for geeks, I just do not know how to set it, what its famous name.
Set Cover Problem - 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));
}